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 $。