Trong đó, ~k = 10^9 + 7~ và ~\%~ là phép chia lấy phần dư, ~|A_{i-1} - A_{i-2}|~ 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 vài phần tử đầu tiên của dãy số ~A~ là: ~5, 7, 2, 9, 7, 16, 9, 25, 16, 41 ...~

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

Dữ liệu vào

• Đọc từ file ODDEVEN.INP gồm một dòng chứa ba số nguyên dương lần lượt là ~x, y, n~. Giữa các số cách nhau bởi một dấu cách.

Kết quả

• Ghi ra file ODDEVEN.OUT một số nguyên là giá trị của ~A_n~.

Giới hạn:

• ~1 \le x, y \le 10^9, 3 \le n \le 10^6~

Ví dụ

Dữ liệu

5 7 8

Kết quả

25