← 返回题目列表

Codeforces · 450/B

B. Jzzhu 和序列

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

Jzzhu发明了一种序列,它们满足以下性质:

$$f_{1} = x; \f_{2} = y; \ \对于所有 i (i \geq 2),f_{i} = f_{i-1} + f_{i+1}。$$

给定 x 和 y,请计算 fn 模 1000000007 (109 + 7)。

输入

第一行包含两个整数 x 和 y (|x|, |y| ≤ 109)。第二行包含一个整数n (1 ≤ n ≤ 2·109)。

输出

输出表示 fn 模 1000000007 (109 + 7) 的单个整数。

示例

输入 #1

2 3
3

输出 #1

1

输入 #2

0 -1
2

输出 #2

1000000006

注意

在第一个示例中,f2 = f1 + f3, 3 = 2 + f3, f3 = 1。

在第二个示例中,f2 = - 1; - 1 模 (109 + 7) 等于 (109 + 6)。