## CERI2018E - A recurrence relation

Our task is to print some terms of the sequence defined by :

• $u_0 = 0$ ;
• $u_1 = 1$ ;
• for $n\geqslant 0$, $u_{n+2} = 5u_{n+1}^2 - 3u_n$.

### Input

The first line of the input consist of a single integer number t which determines the number of tests.

In each of next t lines there is a single integer number n.

#### Constraints

• 0 < t ≤ 30 000
• 0 < n < 1 000 000

### Output

Print un modulo 1 000 000 007

### Example

Input:
3
2
3
10
Output:
5
122
360914800