Fibonacci sequence is defined as
F_n=F_{n-2} + F_{n-1}
with seed numbers
F_1 = 1
and
F_2 = 1.

Teemu wonders how the Fibonacci sequence behaves if he changes the seed numbers to something else. Help Teemu to investigate this matter by providing him a program for computing F_n. As this number may grow quickly, your program should only output result modulo 10^9+7.

Input

The first line of input consists of three numbers F_1, F_2 and n, the seed numbers and the index in Fibonacci sequence.

Output

Output a single line containing F_n modulo 10^9+7.

Limit

• 0 \le F_1 \le F_2 \le 10^9+7
• 1 \le n \le 10^{18}

Example

Input:

1 3 7

Output:

29

The sequence starts \left\lbrace1, 3, 4, 7, 11, 18, 29, 47, 76, \ldots\right\rbrace.