Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Jzzhu and Sequences

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

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

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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/26/2017 21:57:06 (c2).

Desktop version, switch to mobile version.
User lists

Name |
---|