Recurrences
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 274
Solved: 28
- Description
- We often encounter sequence like this, 0, 1, 1, 2, 3, 5, 8, ... , which is called Fibonacci sequence. It's defined by the recurrence
F[0] = 0
F[1] = 1
F[n] = F[n-1] + F[n-2], for n > 1.
Now you need to calculate the value of the kth term mod 1000000009 of the sequence defined by the recurrence below.
G[0] = u
G[1] = v
G[n] = a * G[n-1] + b * G[n-2], for n > 1. - Input
- The input has 30000 cases, one line per case.
Each line contains five integers, u, v, a, b, k. 0<=u, v, a, b, k<=1000000009. - Output
- The value of G[k] mod 1000000009, one line per case.
- sample input
-
0 1 1 1 7 3 5 2 7 6 1 2 3 4 5
- sample output
-
13 5879 614
- hint
- source
- Song Xie