配点 : 100 点
問題文
下一个序列 考虑 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 。具体来说,我做了以下事情: 准备
- 配列 a 使用
- a_{0} = x, \ a_{1} = y, \ a_{i} = 0 \ (i > 1) 初始化 分配
- i = 2, 3, \ldots , N 对于,a_{i} 至 不包括 a_{i-1}+a_{i-2} 代替
在上面的步骤 3 中 按 i 升序更新是正确的 找到 a_{N} 的值。 然而,爱丽丝没有计划,所以 i 已按适当的顺序更新。 此时的更新顺序为 (N-1)! 方法有很多,但每种方法的最终答案都是 找到 a_{N} 中写入的值并添加总和。 计算除以 10^9+7 后的余数。
制約
- 输入均为整数。
- 0 \le x, y \le 10^9
- 2 \le N \le 10^6
入力
输入是按以下格式从标准输入给出的。
x y N
出力
所有更新的最终顺序 a_{N} 值的总和 如果您按照 10^9+7 后的余数。
入力例 1
0 1 3
出力例 1
3
- i 在 2, 3 的顺序更新 a_{N} 的值为 2 ,i 在 3, 2 的顺序更新 a_{N} 的值为 1 总计为 3 。
入力例 2
0 0 5
出力例 2
0
- 无论执行什么顺序,最终的结果都是 写入 a_{N} 的值为 0 。
入力例 3
1 1 6
出力例 3
117
入力例 4
12345 67890 1000000
出力例 4
418969939