#P450B. Jzzhu and Sequences
-
ID: 3034
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Jzzhu and Sequences
No submission language available for this problem.
Description
Jzzhu has invented a kind of sequences, they meet the following property:
You are given x and y, please calculate fn modulo 1000000007 (109 + 7).
The first line contains two integers x and y (|x|, |y| ≤ 109). The second line contains a single integer n (1 ≤ n ≤ 2·109).
Output a single integer representing fn modulo 1000000007 (109 + 7).
Input
The first line contains two integers x and y (|x|, |y| ≤ 109). The second line contains a single integer n (1 ≤ n ≤ 2·109).
Output
Output a single integer representing fn modulo 1000000007 (109 + 7).
Samples
2 3
3
1
0 -1
2
1000000006
Note
In the first sample, f2 = f1 + f3, 3 = 2 + f3, f3 = 1.
In the second sample, f2 = - 1; - 1 modulo (109 + 7) equals (109 + 6).