← 返回题目列表

AtCoder · ttpc2019_j

J. 动态非计划方法

中文机器翻译题面 查看原题

配点 : 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 。具体来说,我做了以下事情: 准备

  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} 的值。 然而,爱丽丝没有计划,所以 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