time limit per test
1 secondmemory limit per test
256 megabytesinput
standard inputoutput
standard outputJzzhu 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).
Sample test(s)
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).
#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, 0, sizeof(res.arr)); for (int i = 0; i < sec; i++) for (int j = 0; j < sec; j++) for (int k = 0; 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, 0, sizeof(res.arr)); for (int i = 0; i < sec; i++) res.arr[i][i] = 1; while (n) { if (n & 1) res = mul(res, ori); ori = mul(ori, ori); n >>= 1; } return res; } int main() { int x, y, n; while (cin >> x >> y >> n) { x = (x + mod) % mod; y = (y + mod) % mod; if (n == 1) cout << x << endl; else if (n == 2) cout << y << endl; else { mat a; a.arr[0][0] = a.arr[1][0] = 1; a.arr[0][1] = -1; a.arr[1][1] = 0; a = expo(a, n - 2); cout << ((a.arr[0][0] * y) % mod + (a.arr[0][1] * x) % mod) % mod << endl; } } return 0; }