The fuzzy number is given by the function F(n) and,

F(n) = 2F(n-1) + 3F(n-2) + n*7ⁿ where F(0) = 1 and F(1) = 1.

Given n, you are to find F(n).

Since the number can be big enough, print the answer modulo 1e9+7.

Constraints:

1<=T<=1e4

1<=n<=1e18

Input Format:

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

T lines follow each containing a number n.

Output Format:

Display the required result for each test case in a new line.