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

• ~Ai~ = |~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