time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Jzzhu has invented a kind of sequences, they meet the following property:
You are given x and y, please calculate f modulo 1000000007 (10 + 7).
Input
The first line contains two integers x and y (|x|, |y| ≤ 10). The second line contains a single integer n (1 ≤ n ≤ 2·10).
Output
Output a single integer representing f modulo 1000000007 (10 + 7).
Sample test(s)
Input
2 3
3
Output
1
Input
0 -1
2
Output
1000000006
Note
In the first sample, f = f + f, 3 = 2 + f, f = 1.
In the second sample, f = - 1; - 1 modulo (10 + 7) equals (10 + 6).
#include <iostream>
#include <cstring>
using namespace std;
/*矩阵快速幂*/
#define mod 1000000007
#define ll long long int
#define sec 2
struct mat
{
ll arr[sec][sec];
};
mat mul(mat a, mat b)
{
mat res;
memset(res.arr, , sizeof(res.arr));
for (int i = ; i < sec; i++)
for (int j = ; j < sec; j++)
for (int k = ; k < sec; k++)
{
res.arr[i][j] = ((res.arr[i][j] + a.arr[i][k] * b.arr[k][j]) % mod + mod) % mod;
}
return res;
}
mat expo(mat ori, int n)
{
mat res;
memset(res.arr, , sizeof(res.arr));
for (int i = ; i < sec; i++)
res.arr[i][i] = ;
while (n)
{
if (n & )
res = mul(res, ori);
ori = mul(ori, ori);
n >>= ;
}
return res;
}
int main()
{
int x, y, n;
while (cin >> x >> y >> n)
{
x = (x + mod) % mod;
y = (y + mod) % mod;
if (n == )
cout << x << endl;
else
if (n == )
cout << y << endl;
else
{
mat a;
a.arr[][] = a.arr[][] = ;
a.arr[][] = -;
a.arr[][] = ;
a = expo(a, n - );
cout << ((a.arr[][] * y) % mod + (a.arr[][] * x) % mod) % mod << endl;
}
}
return ;
}