Fibonacci mở rộng rất lớn


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.