Jzzhu has invented a kind of sequences, they meet the following property:

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

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