Recently Bheem and their friends studied well known fibonacci sequence in their school. Afibonacci sequence is generated by the recursive formula: F[n]=F[n-1]+F[n-2]
where n>1 and F[0]=F[1]=1. Then Bheem started playing with similar type of sequences. In this process he came up with generalized tetranacci numbers.
Generalized tetranacci numbers are defined by following recurrence relation:
T[n] = a*T[n-1] + b*T[n-2] + c*T[n-3] + d*T[n-4] +e (n>4)
where T[1], T[2], T[3] and T[4]can be any given integer.

Bheem tried to calculate the value of this sequence upto a given number n, but he was unable to calculate the value of n^th term instantly.
Given the values of n, a, b, c, d, e, T[1], T[2], T[3] and T[4]. Help Bheem calculate the value of T[n]. As the answer can be very large, output the answer modulo 1000000007.
Note: The answer should always be a positive integer.

 

Input

• The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows
• The first line of each test case contains a single integer n.
• The second line of each test cases contains 9 separated integers a, b, c, d, e, T[1], T[2], T[3] and T[4].

 

Output

• For each test case, output a single line containing the answer to given problem modulo 1000000007

 

Constraints

• 1 = T = 1000