Một nhà khoa học nghiên cứu về sự phát triển của một loại vi khuẩn đặc biệt trong phòng thí nghiệm. Tại ngày thứ \(n\), số lượng vi khuẩn \(F(n)\) sẽ thay đổi theo công thức:

trong đó:

• \(F(n-1)\) là số vi khuẩn của ngày hôm trước.
• \(2F(n-2)\) đại diện cho số vi khuẩn phát triển từ thế hệ của hai ngày trước, do chúng có tốc độ nhân đôi.
• \(3n^2\) là số vi khuẩn mới xuất hiện do ảnh hưởng của môi trường và chất dinh dưỡng được bổ sung.

Ban đầu, nhà khoa học ghi nhận số lượng vi khuẩn là:

• \(F(0) = a\) (số lượng vi khuẩn ban đầu)
• \(F(1) = b\) (số lượng vi khuẩn sau ngày đầu tiên)

Bắt đầu từ ngày thứ hai, số lượng vi khuẩn tăng theo công thức trên.

Cho biết trước các giá trị \(a, b\) và \(n\), bạn hãy giúp nhà khoa học viết chương trình tính \(F(n)\). Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(10^9 + 7\).

Input

• Một dòng duy nhất chứa ba số nguyên \(a, b, n\) (\(1 \leq a \leq b \leq 10^{18}, 1 \leq n \leq 10^{18}\)).

Output

• In ra phần dư của \(F(n)\) khi chia cho \(10^9 + 7\).

Example

1 2 3

47

100 200 300

747496743

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(a, b \leq 10^9, n \leq 10^6\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.