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.