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