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≤2109).
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).
本来9点的CF,今天有学姐来,讲到了9点半,这题最后没注意坑点,最后判的时候还wa了,掉了100分,蛋疼中
#include
#include
#include
#include
using namespace std; const int maxn=1100; const int M=1000000007; int a[maxn]; int main() { int x,y,n; while(cin>>x>>y>>n) { a[1]=x; a[2]=y; int len=0,t; for(int i=3;;i++) { a[i]=a[i-1]-a[i-2]; if(a[i]==a[2]&&a[i-1]==a[1]&&i>=4) { len=i-2; break; } if(i>=n) break; } if(len) { // cout<<"len:"<
0) cout<