Jzzhu has invented a kind of sequences, they meet the following property:
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).
Example
Input
2 3
3
Output
1
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).
题意 ： 显然是矩阵快速幂么
坑点 ： 就是数论取模这一块 ， 稍不注意就错了
const ll mod = 1e9+7;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a struct mat
{
ll a[2][2];
}; mat mul(mat a, mat b){
mat r;
memset(r.a, 0, sizeof(r.a)); for(int i = 0; i < 2; i++){
for(int k = 0; k < 2; k++){
if (a.a[i][k]){
for(int j = 0; j < 2; j++){
if (b.a[k][j]){
r.a[i][j] += (a.a[i][k] * b.a[k][j] + mod)%mod;
r.a[i][j] = (r.a[i][j] + mod)%mod;
}
}
}
}
}
return r;
} mat pow(mat a, int n){
mat b; for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
if (i == j) b.a[i][i] = 1;
else b.a[i][j] = 0; while(n){
if (n & 1) b = mul(a, b);
a = mul(a, a);
n >>= 1;
}
return b;
} int main() {
ll x, y, n; scanf("%lld%lld%lld", &x, &y, &n);
mat a;
a.a[0][0] = a.a[1][0] = 1;
a.a[0][1] = -1;
a.a[1][1] = 0; if (n == 1){
printf("%lld\n", (x+mod)%mod);
}
else if (n == 2){
printf("%lld\n", (y+mod)%mod);
}
else {
a = pow(a, n-2);
ll ans = ((a.a[0][0]*y+mod)%mod + (a.a[0][1]*x+mod)%mod + mod)%mod; // 重点就是这里
//ll ans = (a.a[0][0]*y+a.a[0][1]*x+mod)%mod;
//ans = (ans + mod)%mod;
printf("%lld\n", ans );
} return 0;
}
/*
-9 -11
12345
*/