Jzzhu and Sequences

题意翻译

Jzzhu发明了一种序列,它们有以下性质: **f(1)=x; f(2)=y; (对任意i, i>=2) , f(i)=f(i-1)+f(i+1)** 给出 x,y ,现请你计算出 f(n) mod 1000000007 (10^9+7) 的值。 输入 第一行包含2个整数x和y,(|x|, |y|<= 10^9)。第二行包含1个整数n,(1<=n<=2*10^9)。 输出 一行。输出一个整数** f(n)**模1000000007(10^9+7)的值

题目描述

Jzzhu has invented a kind of sequences, they meet the following property: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF450B/24eb04dd3b6c3e1abcf8e078661c78665e8d1d86.png)You are given $ x $ and $ y $ , please calculate $ f_{n} $ modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出格式

输入格式


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 a single integer representing $ f_{n} $ modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

2 3
3

输出样例 #1

1

输入样例 #2

0 -1
2

输出样例 #2

1000000006

说明

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