Personal Contest 2010.07.20 (public)

From: 2010-07-20 12:00:00 To: 2010-07-20 15:00:00 Now: 2017-09-22 06:52:07 Status: Public

C - The value of F[n]

Time Limit: 1s Memory Limit: 128MB

Submissions: 161 Solved: 72
Description

For any integer i>=3 we have  F[i]=(F[i-1]+2*F[i-2]+3*F[i-3])%9901;

Now give you F[0],F[1],F[2],can you tell me the value of F

Input

Fist Line, an integer Q(1<=Q<=100) represent the number of cases;

Every case is a line of four integers:F[0],F[1],F[2],n;

(0<=F[0],F[1],F[2]<9901,0<=n<100000000)

Output

For each case ,you are request to output one integer the value of F[n] in one line.

Sample Input
4
1 2 3 3
4 5 6 5
2 3 4 2
4 5 6 100000
Sample Output
10
129
4
6086
Hint
Source
Dongxu LI