Ada the Ladybug was playing chess agains her good friend Velvet Mite Vinit. They came up with new figure, called palace. In fact, palace is just tower with king inside. It can attack as king and tower combined: Either anywhere to same column or row or anywhere to adjacent (by side or diagonal) field.

Their question is simple: How many ways can N palaces be placed on NxN chessboard so none of them attacks any other. Since this number might be pretty big, output answer modulo 10⁹+7

Input

The first line of input will contain 1 ≤ T ≤ 10⁵, the number of test-cases.

Each of the testcases will contain single integer 1 ≤ N ≤ 10⁷, the size of chessboard.

Output

For each test-case output the number of possibilities modulo 1000000007.

Example Input

8
1
2
3
7
10
1000
10000
9999999

Example Output

1
0
0
646
479306
711794305
450342414
838796194