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 ≥ 3 và i chỉ số chẵn
• ~A_i = |A{i-1} - A{i-2}|%k~ nếu ~i ≥ 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 An.

Input

• 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 ≤ x, y ≤ 10^9, 3 ≤ n ≤ 10^6~)

Output

• Một số nguyên là giá trị của An.

Example

Input

5 7 8

Output

25