题目描述

Jzzhu 发明了一种序列，它们有以下性质：

• $f(1)=x$；
• $f(2)=y$；
• 对任意 $i\ge 2$，$f(i)=f(i-1)+f(i+1)$。

给出 $x,y$，现请你计算出 $f(n) \mod (10^9+7)$ 的值。

输入格式

第一行包含 $2$ 个整数 $x$ 和 $y$，$|x|, |y|\le 10^9$。

第二行包含 $1$ 个整数 $n$，1\le n\le 2\times 10^9$。

输出格式

输出一个整数表示答案，对 $(10^9+7)$ 取模。

2 3
3

1

0 -1
2

1000000006