Ram loves solving mathematical series.Recently Shyam challenged him to solve the following series

s(n) = f(n) if n < 5

s(n) = s(n-1) + s(n-2) + s(n-3) + 2*s(n-4) + s(n-5) else

He tried solving the series but is not able to solve.

So he has asked for your help.

Help him in solving the series.

Calculate the value of s(n) Mod 1000000007.

Constraints:

t <= 10^3

n <= 10^9

0 < f(0), f(1), f(2), f(3), f(4) <= 10^6

Input :

First line contains t the number of test cases.

In test case consists of 2 lines,

First line contain 5 space separated integers containing the values of f(0), f(1), f(2), f(3), f(4) respectively.

Second line contains a single integer n.

Output :

T lines each containing the value of s(n) Mod 1000000007.

To be eligible for prizes you have to register for AlgoXtreme at the Zeitgeist site. To register visit Zeitgeist. Only those candidates who have registered on the Zeitgeist website for the AlgoXtreme contest will be eligible to avail the Prizes.