CodeForces

题目链接：https://vjudge.net/problem/CodeForces-450B

Jzzhu has invented a kind of sequences, they meet the following property:

$\text{[math]}$

You are given x and y, please calculate fn modulo 1000000007 (109 + 7).

Input

The first line contains two integers x and y (|x|, |y| ≤ 109). The second line contains a single integer n (1 ≤ n ≤ 2·109).

Output

Output a single integer representing fn modulo 1000000007 (109 + 7).

Examples

input

2 3
3

output

input

0 -1
2

output

1000000006

Note

In the first sample, f2 = f1 + f3, 3 = 2 + f3, f3 = 1.

In the second sample, f2 = - 1; - 1 modulo (109 + 7) equals (109 + 6).

题解：

斐波那契数，递推式为：f[n] = f[n-1] - f[n-2]，构造矩阵如下：

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int MOD = 1e9+7;
17 const int MAXN = 1e6+100;
18 
19 const int Size = 2;
20 struct MA
21 {
22     LL mat[Size][Size];
23     void init()
24     {
25         for(int i = 0; i<Size; i++)
26         for(int j = 0; j<Size; j++)
27             mat[i][j] = (i==j);
28     }
29 };
30 
31 MA mul(MA x, MA y)
32 {
33     MA ret;
34     memset(ret.mat, 0, sizeof(ret.mat));
35     for(int i = 0; i<Size; i++)
36     for(int j = 0; j<Size; j++)
37     for(int k = 0; k<Size; k++)
38         ret.mat[i][j] += (1LL*x.mat[i][k]*y.mat[k][j])%MOD, ret.mat[i][j] %= MOD;
39     return ret;
40 }
41 
42 MA qpow(MA x, LL y)
43 {
44     MA s;
45     s.init();
46     while(y)
47     {
48         if(y&1) s = mul(s, x);
49         x = mul(x, x);
50         y >>= 1;
51     }
52     return s;
53 }
54 
55 MA tmp = {
56     1, -1,
57     1, 0
58 };
59 
60 int main()
61 {
62     LL f[3], n;
63     while(scanf("%lld%lld%lld",&f[1],&f[2],&n)!=EOF)
64     {
65         if(n<=2)
66         {
67             printf("%lld
", (f[n]+MOD)%MOD);
68             continue;
69         }
70 
71         MA s = tmp;
72         s = qpow(s, n-2);
73         LL ans = (1LL*s.mat[0][0]*f[2]%MOD+1LL*s.mat[0][1]*f[1]%MOD+2*MOD)%MOD;
74         printf("%lld
", ans);
75     }
76 }

View Code