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
© 2015 HUST ACMICPC TEAM. All Right Reserved.