You-know-who loves recurrence relations and second order recurrence in particular.

He-who-must-not-be-named defines:

F(n) = a*F(n-1)+b*F(n-2) , n>1
Where

F(0) and

F(1) are already known to him.

Being a great lover of recurrences he set the destruction password for one of his horcruxes as

S(K,N).
Where

Now Harry wants to destroy this horcrux but is unable to do so because he is a wizard, not a programmer. You must help him to save the magical word. Your task is to calculate the password for Harry.

Input format:
First line of input contains two space separated integers

F(0) and

F(1).

Second line of input contains two space separated integers

a and

b.

Third line of input contains a single integer

P.

Last line of input contains two space separated integers

N and

K.

Output format:
Single integer denoting the value of

S(K,N).

Constraints:
0 < F(0) , F(1) < 1e7

0 < a,b < 100

1e7 < P < 1e9 , P is prime

0 < N < 1e18

0 < K < 5e6

Sample Input:
1 1

1 1

10000019

20 1

Sample Output:
28655