Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
134 - ZOJ Monthly, June 2014 - A
Another Recurrence Sequence

Time Limit: 5 Seconds      Memory Limit: 131072 KB

All the description is the formula below.

f(n)=\begin{cases}0, &n<0 \cr1, &n=0\cr Af(n-a)+Bf(n-b), &n>0\end{cases}

Input

One line per case, A, B, a, b, n, one by one. All of them are possitive integers less than 1000000000.

Output

One line per case, output f(n) mod 5767169.

Sample Input

1 1 1 2 6
1 2 3 4 24

Sample Output

13
345

Author: ZHOU, Yuchen
Submit    Status