Hey!

I was asked this question in my C-Programming assignment in college. I tried submitting a solution but got TLE. Could anybody please tell me how I could optimize it? Just give me a hint or what I have to use. I want to do it on my own.

Thanks!

Here goes the question :

We all know what Fibonacci numbers are (The sequence of numbers such that every number

in the sequence is the sum of the previous two numbers in the sequence, with the first two

numbers 0 and 1)

f(n) = f(n − 1) + f(n − 2)

f(1) = 0 f(2) = 1

Now lets define a new kind of Fibonacci numbers, the iFibo Numbers.

The iFibo numbers are defined as the sequence of numbers, such that every number in the

sequence is the sum of A times the previous number, B times the number before the previous

number, and C times the number before the number before the previous number in the

sequence, with the first two iFibo numbers equal to D, E and F.

f(n) = A * f(n − 1) + B * f(n − 2) + C * f(n − 3)

f(1) = D f(2) = E f(3) = F

Now, your task is simple. Given N, A, B, C, D, E, F you need to tell the Nth iFibo number (mod

10000007).

Input

The first line contains T. Next T lines contain 7 space separated integers N A B C D E F.

Output

For each testcase, output in a single line, the Nth iFibo number, mod 10000007.

Constraints

0 <= A, B, C, D, E, F < 10000007

For 80% score

0 <= T <= 50

1 <= N <= 100000

For 100% score

0 <=T <= 100000

1 <= N <= 10^12

SampleInput

3

5 1 1 0 1 1 2

4 1 1 1 1 1 1

10 2 0 2 1 2 3

Sample output

5

3

1424