Jzzhu has invented a kind of sequences, they meet the following property:$f_{1} = x ; f_{2} = y ; \forall i(i \geq 2), f_{i} = f_{i - 1} + f_{i + 1}$

You are given x and y, please calculate f_{n} modulo 1000000007 (10^9 + 7).


-----Input-----

The first line contains two integers x and y (|x|, |y| ≤ 10^9). The second line contains a single integer n (1 ≤ n ≤ 2·10^9).


-----Output-----

Output a single integer representing f_{n} modulo 1000000007 (10^9 + 7).


-----Examples-----
Input
2 3
3

Output
1

Input
0 -1
2

Output
1000000006



-----Note-----

In the first sample, f_2 = f_1 + f_3, 3 = 2 + f_3, f_3 = 1.

In the second sample, f_2 =  - 1;  - 1 modulo (10^9 + 7) equals (10^9 + 6).

Difficulty: interview

Starter code:

Solutions:
def main():
    x, y = [int(i) for i in input().split()]
    n = int(input())
    
    result = [x, y, y - x, -x, -y, x - y][(n - 1) % 6]
    
    print(result % 1000000007)


main()


x, y = list(map(int, input().split()))
n = int(input())
r = [x, y, y - x, -x, -y, x - y]
print(r[(n-1) % len(r)] % 1000000007)


x,y=map(int,input().split())
n=int(input())
z=y-x
if n%6==1:
	print(x%1000000007)
elif n%6==2:
	print(y%1000000007)
elif n%6==3:
	print(z%1000000007)
elif n%6==4:
	print((-x)%1000000007)
elif n%6==5:
	print((-y)%1000000007)
else:
	print((-z)%1000000007)

def main():
    x, y = input().split()
    n = int(input())
    f = [int(x), int(y)]
    while len(f) < 6:
        f.append(f[-1] - f[-2])
    print(f[n % 6 - 1] % 1000000007)

main()


x, y = map(int, input().split())
n = int(input())
z = y - x
var = [x, y, z, -x, -y, -z]
print(var[(n - 1) % 6] % 1000000007)

'''
f[i] = f[i - 1] - f[i - 2]
f[i] = -f[i - 3]
f[i] = -f[i - 4] + f[i - 5]
f[i] = f[i - 6]
'''

m = list(map(int, str.split(input())))
for _ in range(2, 6):

    m.append(m[-1] - m[-2])

print(m[(int(input()) - 1) % 6] % (10 ** 9 + 7))


#!/usr/bin/env python3

def main():
    x, y = list(map(int, input().split()))
    n = int(input())

    lst = [x, y, y - x, -x, -y, x - y]
    lst = list([a % 1000000007 for a in lst])

    print(lst[(n - 1) % len(lst)])

def __starting_point():
    main()

__starting_point()

x, y = list(map(int, input().split()))
n = int(input())

s = (n - 1) % 6

if s == 0:
    print(x % 1000000007)
if s == 1:
    print(y % 1000000007)
if s == 2:
    print((y - x) % 1000000007)
if s == 3:
    print((-x) % 1000000007)
if s == 4:
    print((-y) % 1000000007)
if s == 5:
    print((x - y) % 1000000007)

x, y = tuple(map(int, input().split(' ')))
n = int(input()) - 1
a = (x, y, y - x, -x, -y, -y + x)
#print(a)

print(a[n%6]%1000000007)

from sys import stdin as cin
from fractions import gcd
mod = 1000000007
x,y = list(map(int,cin.readline().split()))
n = int(cin.readline())
k = n%6
if k==0:
    print((x-y)%mod)
elif k==1:
    print(x%mod)
elif k==2:
    print(y%mod)
elif k==3:
    print((y-x)%mod)
elif k==4:
    print(-x%mod)
elif k==5:
    print(-y%mod)











a = [0, 0, 0]
a[0], a[1] = list(map(int, input().split()))
n = int(input()) - 1;
N = 1000000007
a[2] = a[1] - a[0];
if (n // 3) % 2: 
    print((-a[n % 3]) % N)
else:
    print(a[n % 3] % N)



f = [0]*7
f[1], f[2] = [int (x) for x in input().split()]
f[3] = f[2] - f[1]
f[4] = -f[1]
f[5] = -f[2]
f[6] = -f[3]
n = int(input())
t = n%6
if(t == 0): t = 6
print((f[t])%1000000007)


x,y = list(map(int, input().split()))
n = int(input())
result = n%6
if result == 1:
    print(x%1000000007)
elif result == 2:
    print(y%1000000007)
elif result == 3:
    print((y-x)%1000000007)
elif result == 4:
    print((-x)%1000000007)
elif result == 5:
    print((-y)%1000000007)
elif result == 0:
    print((x-y)%1000000007)
    





mod = 1000000007
a, b = list(map(int, input().split()))
n = int(input())

c = b - a

if n % 3 == 1:
    if (n-1)/3 % 2 == 0:
        print((mod+a)%mod)
    else:
        print((mod-a)%mod)
elif n % 3 == 2:
    if (n-2)/3 % 2 == 0:
        print((mod+b)%mod)
    else:
        print((mod-b)%mod)
else:
    if (n-3)/3 % 2 == 0:
        print((mod+c)%mod)
    else:
        print((mod-c)%mod)




sa=input().split(' ')
x=int(sa[0])
y=int(sa[1])
n=int(input())

def generate(x, y, n):
    sa=[x, y, y-x, -x, -y, x-y]
    return sa[((n%6)-1)%6]

print(generate(x, y, n)%(10**9+7))

x,y=list(map(int,input().split()))
n=int(input())
def modulo(a):
    if a==1000000007:
        return 0
    elif a>=0:
        return int(a%(1000000007))
    else:
        if a%1000000007==0:
            return 0
        else:
            return int((1000000007)-int(((-1)*a)%(1000000007)))
n=n%6
if n==1:    print(modulo(x))
elif n==2:  print(modulo(y))
elif n==3:  print(modulo(y-x))
elif n==4:  print(modulo(-x))
elif n==5:  print(modulo(-y))
elif n==0:  print(modulo(x-y))

x,y=list(map(int,input().split()))
n=int(input())
z=y-x
if(n==1):
    print(x%1000000007)
elif(n==2):
    print(y%1000000007)
elif(n==3):
    print(z%1000000007)
else:
    mod=n%3
    if(mod==0):
        if((n//3)%2==0):
            print((-1*z)%1000000007)
        else:
            print(z%1000000007)
    elif(mod==1):
        if((n//3)%2==1):
            print((-1*x)%1000000007)
        else:
            print(x%1000000007)
    else:
        if((n//3)%2==1):
            print((-1*y)%1000000007)
        else:
            print(y%1000000007)


x, y = map(int, input().split())
n = int(input())
f = [x, y, y - x, -x, -y, x - y]
print(f[(n - 1) % len(f)] % 1000000007)

mod = 1000000007
x, y= map(int, input().split())
n = int(input())
A = [x - y, x, y, y - x, -x, -y]
n %= 6
print((A[n]%mod + mod)%mod)

mod = 10**9 + 7
x, y= map(int, input().split())
n = int(input())
A = [x - y, x, y, y - x, -x, -y]
n %= 6
print((A[n])%mod)

x, y = tuple(map(int, input().split()))
n = int(input())

answers = [x, y, y - x, -x, -y, -y + x]
print(answers[n % 6 - 1] % (10 ** 9 + 7))


x,y = map(int, input().split())
n = int(input())
INF = 10**9+7
if n == 1:
    print(x%INF)
elif n == 2:
    print(y%INF)
else:
    n=n%6
    a=[x,y,y-x,-x,-y,x-y]
    print(a[n-1]%INF)

i = input().split()
f1 = int(i[0])
f2 = int(i[1])

n = int(input()) % 6
l = []
for x in range(n+6):
    l.append(0)

l[0] = f1
l[1] = f2
for x in range(2, n+6):
    l[x] = (l[x-1] - l[x-2])

print(l[n-1] % 1000000007)