题目链接：http://codeforces.com/problemset/problem/450/B
题意很好懂，矩阵快速幂模版题。
/*
| 1, -1 | | fn |
| 1, 0 | | fn-1 |
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef __int64 LL;
LL mod = 1e9 + ;
struct data {
LL mat[][];
}; data operator* (data a , data b) {
data res;
for(int i = ; i <= ; i++) {
for(int j = ; j <= ; j++) {
res.mat[i][j] = ;
for(int k = ; k <= ; k++) {
res.mat[i][j] = ((a.mat[i][k]*b.mat[k][j] % mod) + res.mat[i][j]) % mod;
}
}
}
return res;
} data operator^ (data a , LL n) {
data res;
for(int i = ; i <= ; i++) {
for(int j = ; j <= ; j++) {
res.mat[i][j] = (i == j);
}
}
while(n) {
if(n & )
res = a * res;
a = a * a;
n >>= ;
}
return res;
} int main()
{
data res;
LL n;
cin >> res.mat[][] >> res.mat[][] >> n;
if(n == ) {
cout << (res.mat[][] % mod + mod) % mod << endl;
}
else if(n == ) {
cout << (res.mat[][] % mod + mod) % mod << endl;
}
else {
data a;
a.mat[][] = a.mat[][] = ;
a.mat[][] = ;
a.mat[][] = -;
a = a ^ (n - );
res = a * res;
cout << (res.mat[][] % mod + mod) % mod << endl;
}
}