Bé Bo đang học về tính lẻ chẵn. Hôm nay, cô giáo dạy toán cho Bo bài toán như sau:

Cho hai số nguyên dương \(x,y\). Dãy số \(A\) được xây dựng theo quy tắc sau:

+ \(A_{1} = x\)

+ \(A_{2} = y\)

+ \(A_{i} = \left( A_{i - 1} + A_{i - 2} \right)\% k\) nếu \(i \geq 3\) và \(i\) là chỉ số chẵn

+ \(A_{i} = \left| A_{i - 1} + A_{i - 2\ } \right|\% k\) nếu \(i \geq 3\) và \(i\) là chỉ số lẻ.

Trong đó \(k = 10^{9} + 7\) và \(\%\) là phép chia lấy dư, \(\left| A_{i - 1} + A_{i - 2} \right|\) là giá trị tuyệt đối của \(A_{i - 1} - A_{i - 2}\).

Ví dụ: với \(x = 5,\ y = 7\) thì một số phần tử đầu tiên của dãy số \(A\) là: \(5,7,2,9,7,16,9,25,16\ldots\)

Cho trước số nguyên dương \(n\), em hãy cho biết số \(A_{n}\) có giá trị là bao nhiêu?

Dữ liệu vào:

+ Một dòng chứa 3 số nguyên dương lần lượt là \(x,\ y,\ n\ (1 \leq x,y \leq 10^{9},3 \leq n \leq 10^{6}\)

Kết quả:

+ Ghi một số nguyên duy nhất cho kết quả bài toán

Ví dụ:

Input	Output
5 7 8	25