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