AT_ttpc2019_j.動的無計画法

考虑以下数列 $ a\ =\ (a_0,\ a_1,\ \ldots\ ,\ a_N) $。

$ \begin{aligned}\ a_i\ =\ \begin{cases}\ x\ &\ (\ i\ =\ 0\ )\ \ y\ &\ (\ i\ =\ 1\ )\ \ a_{i-1}\ +\ a_{i-2}\ &\ (\ \text{otherwise}\ )\ \end{cases}\ \end{aligned} $

Alice决定使用动态规划来求解 $ a_N $。具体做法如下：

1. 准备数组 $ a $
2. 初始化 $ a_{0}\ =\ x,\ a_{1}\ =\ y,\ a_{i}\ =\ 0\ (i\ >\ 1) $
3. 对于 $ i\ =\ 2,\ 3,\ \ldots\ ,\ N $，将 $ a_{i} $ 替换为 $ a_{i-1}+a_{i-2} $

按照上述步骤中的第3步，逐渐以较小的 $ i $ 进行更新，就能得到正确的 $ a_{N} $ 值。然而，Alice没有计划，随意更新了 $ i $ 的顺序。此时，更新的顺序有 $ (N-1)! $ 种可能，要求出每种顺序下最终写入 $ a_{N} $ 的值，并计算它们的总和除以 $ 10^9+7 $ 的余数。

输入以以下格式从标准输入中给出。

$ x $ $ y $ $ N $

输出在所有更新顺序下最终 $ a_{N} $ 的值的总和除以 $ 10^9+7 $ 的余数。

样例#1

样例输入 #1

0 1 3

样例输出 #1

3

样例 #2

样例输入 #2

0 0 5

样例输出 #2

0

样例 #3

样例输入 #3

1 1 6

样例输出 #3

117

样例 #4

样例输入 #4

12345 67890 1000000

示例输出 #4

418969939

• 输入为整数
• $ 0\ \le\ x,\ y\ \le\ 10^9 $
• $ 2\ \le\ N\ \le\ 10^6 $

样例解释 1

当按照 $ i $ 的顺序更新为 $ 2,\ 3 $ 时，$ a_{N} $ 的值为 $ 2 $；当按照 $ i $ 的顺序更新为 $ 3,\ 2 $ 时，$ a_{N} $ 的值为 $ 1 $，总和为 $ 3 $。

样例解释 2

无论操作顺序如何，最终 $ a_{N} $ 写入的值始终为 $ 0 $。