1333 - Recurrences

Time Limit: 1s Memory Limit: 128MB

Submissions: 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