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