Consider the following n×n matrix:

Calculate the determinant of such matrix given some n

Input

The first line of the input contains number t – the number of tests. Then t test descriptions follow. Each test consist of a single integer n.

Constraints

1 <= t <= 1000
1 <= n <= 10¹⁵

Output

For each test print the determinant of the matrix modulo 1000000007.

Example

Input:
3
1
2
3

Output:
1
2
3