Dãy số của Jzzhu

Xét dãy số $f$ thoả mãn tính chất sau với mọi $i\ge 2$:

$$f_i=f_{i-1}+f_{i+1}$$

Cho trước $f_1=x$ và $f_2=y$. Hãy tính $f_n$ lấy dư cho $1000000007$ (${10}^9+7$).

Lưu ý rằng $f_n$ có thể là số âm; khi đó kết quả lấy dư được quy về khoảng $[0,{10}^9+6]$ (ví dụ $-1$ có kết quả là ${10}^9+6$).

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên $x$ và $y$.
• Dòng thứ hai chứa một số nguyên $n$.

Dữ liệu ra

Một số nguyên duy nhất là $f_n$ lấy dư cho ${10}^9+7$.

Ràng buộc

• $|x|,|y|\le {10}^9$
• $1\le n\le 2·{10}^9$

Ví dụ