Dãy Fibonacci tùy biến
Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó.
Như vậy, nếu ta gọi $f_1$ là số fibonacci tùy biến thứ nhất, $f_2$ là số fibonacci tùy biến thứ hai, ..., ta có:
- $f_1=a$;
- $f_2=b$;
- $f_i =f_{i−1} +f_{i−2}$ với $i \ge 3$.
Cho số nguyên $N$. Hãy tìm số Fibonacci tùy biến thứ $N$.
Dữ liệu
- Dòng duy nhất chứa ba số nguyên dương $a,b,N \ (1\le a,b \le 10^5; 1\le N \le 10^6)$.
Kết quả
- Kết quả bài toán sau khi chia lấy dư cho $10^9+7$.
Ví dụ
Ví dụ 1
input
1 1 10
output
55
Ví dụ 2
input
5 4 5
output
22
Comments