Gosain loves sport cars. Gosainâ€™s boss, PKD, had a Lamborghini. PKD saw the love that Gosain had for cars, so he decided to give his car to Gosain, if can answer a question.

Given these 2 recurrences :

f(n) = f(n-1) + 2*g(n-2) + (5^{n})*(n^{3}), n ≥2

g(n) = 3*g(n-1) + 4*f(n-2) + (5^{n})*(n^{4}), n ≥2

and given that :

f(0) = 0 and f(1) = 1

g(0) = 1 and g(1) = 2

Gosain is supposed to find the value of f(N) modulo 1000000007 for some given N. Can you help him?

Input Format :

The first line of input contains T, the number of test cases.

Next T lines each contain an integer N for the corresponding test case.

Output Format :

Print the answer for each test case in a new line.

Constraints :

1 ≤ T ≤ 2000

0 ≤ N ≤ 10^{18}

Sample Input :

5

1

2

3

4

5

Sample Output :

1

203

3582

44394

457713

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

9 months ago

cpp

0.59 sec

308 KB

9 months ago

cpp

1.26 sec

464 KB

9 months ago

cpp

0.64 sec

312 KB