You-know-who loves recurrence relations and second order recurrence in particular.
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).
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.
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.
Single integer denoting the value of S(K,N).
0 < F(0) , F(1) < 1e7
0 < a,b < 100
1e7 < P < 1e9 , P is prime
0 < N < 1e18
0 < K < 5e6