Kodi the cricketer

4.6

5 votes
Easy
Problem

Kodi has been bought at the auction in the NIT Premier League. Kodi is a batsman and the runs he makes in each innings depends on the runs he has made in his previous three innings. The runs he makes in the current innings is given by the formula :

F(x) = ( 2xF(x-1)-(x-1)F(x-2)-(x-2)*F(x-3) )/3

where F(i) = runs Kodi makes in ith innings

The number of innings Kodi plays can be infinite.

When x is given , find F(x)

Input

first line contains T . no of test cases

next t lines contains F(0),F(1),F(2) and x .

Output

F(x)

Constraint

0 < T < 100

0 <= x <= 1000000

0 <= F(i) <= 100000

F(0)=F(1)=F(2)

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?