1333  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[n1] + F[n2], 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[n1] + b * G[n2], 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