4.The Cricket Match

Credits:200

There was so much of fun and frolic all around since the world cup was around the corner. As with any world Cup there was also a lot of betting , particularly on one batsman, Sachin Tendulkar. But a Mathematics Professor from Madras Institute of Technology has found a recurrence in the way sachin scores in the nth match. It is as follows

f(1)=a1

f(2)=a2

f(3)=a3

f(n)=(a*f(n-1)+b*f(n-2)+c*f(n-3))%r

So u have to help the people who bet on Sachin by computing the value of f(n) given a1,a2,a3,a,b,c,n,r. Can you?

INPUT:

There are multiple test cases. The first line consists of a single integer denoting the number of test cases , m.The next m lines contain eight numbers each a1,a2,a3,a,b,c,n,r in that order. 1<=n<=2^62 ,1< r<=10^6 and 1<= a1,a2,a3,a,b,c<=10000

OUTPUT:

Output a single number in each line giving the value of f(n) for each test case.

SAMPLE INPUT:
2
1 2 3 5 2 3 5 3
1 2 3 5 2 3 6 7

SAMPLE OUTPUT:
2
0