cf#257(Div.2) B. Jzzhu and Sequences_html/css_WEB-ITnose

B. Jzzhu and Sequences

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 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 33

output

input

0 -12

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

题意：给你一个递推式，f2=f1 f3-->变形为：f[i]=f[i-1]-f[i-2];输入f[1]和f[2]；求第n个数的值；如果你想打表的话劝你放弃吧！肯定会超时的，还记得高中的等差序列吗！对这绝对是一个周期序列！而且周期为6；

#include<stdio.h>int main(){   __int64 a[10],x,y,n;    int i;    scanf("%I64d%I64d",&x,&y);    a[1]=x;a[2]=y;    for(i=3;i<=6;i++)        a[i]=a[i-1]-a[i-2];    a[0]=a[6];    scanf("%I64d",&n);    n=n%6;    while(1)    {        if(a[n]<0)            a[n]+=1000000007;        else break;    }    printf("%I64d\n",a[n]%1000000007);    return 0;}