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:

• ~A_1 = x~
• ~A_2 = y~
• ~A_i = (A_{i-1} + A_{i-2})\ \%\ k~ nếu ~i \ge 3~ và ~i~ là chỉ số chẵn
• ~A_i = |A_{i-1} - A_{i-2}|\ \%\ k~ nếu ~i \ge 3~ và ~i~ là chỉ số lẻ

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, ...~

Yêu cầu

Cho trước số nguyên dương ~n~, hãy tính ~A_n~.

Dữ liệu đầu vào

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 ~(1 \le x, y \le 10^9,\ 3 \le n \le 10^6)~.

Dữ liệu đầu ra

Gồm một số nguyên là giá trị của ~A_n~.

Ví dụ

Ví dụ 1

INPUT

5 7 8

OUTPUT

25