（CF#257)B. Jzzhu and Sequences - c++编程基础

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).

Sample test(s) input

2 3
3

output

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<