Fibonacci mở rộng rất lớn
Cho dãy $f$ được định nghĩa như sau:
- $f_1=a$;
- $f_2=b$;
- $f_i=c\times f_{i-1}+d\times f_{i-2}$ với $i \ge 3$.
Hãy tìm giá trị của $f_N$.
Dữ liệu
- Một dòng duy nhất chứa năm số nguyên $a,b,c,d,N \ (0<a,b,c,d<10^9;1\le N\le 10^{18})$.
Kết quả
- Kết quả bài toán sau khi chia lấy dư cho $10^9+3$.
Ví dụ
Ví dụ 1
input
1 2 1 1 5
output
8
Comments