Integer Sequence

Given x, y, the last two digits of A0 and A1, and a large index n, print the last two digits of An where An = x*An-1 + y*An-2.

Medium5MathDynamic programmingSimulationBit manipulationInterviewNo attempts yetTime limit0.25sMemory limit512 MB

Description

Examples2

Problem

There is a sequence of non-negative integers $A_0, A_1, A_2, A_3, \ldots$ .

For every $n \ge 2$ , the sequence satisfies $A_n = x \times A_{n-1} + y \times A_{n-2}$ .

Given the last two digits of $A_0$ and $A_1$ , write a program that finds the last two digits of $A_n$ .

For example, if $x = y = 1$ , $A_0 = 0$ , and $A_1 = 1$ , the sequence is $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$ . The last two digits of $A_{10}$ are $55$ .

Input

The first line contains $x$ , $y$ , $a_0$ , $a_1$ , and $n$ , separated by spaces. ( $1 \le x, y \le 99$ , $0 \le n < 10^8$ )

$a_0$ and $a_1$ are the last two digits of $A_0$ and $A_1$ , respectively. They are always written with two digits; a value below 10 has a leading zero, as in 07.

Output

Print the last two digits of $A_n$ . Always print exactly two digits: if the value is below 10, add a leading zero, as in 07.