You may have come across questions like, Match-The-Following words with their synonyms in the second column and alike. Ted also stumbled upon one such question. Being weak at English, he tried guessing the answers. While he guessed, he thought about how unlucky he was at guessing.

Being also weak at math, he needs help from you for a slightly different task. Find the total number of ways of completing the solution to this question in which he gets none of the matches correct.

Note: In the match-the-following problem, there are two columns of words. Each column contains N words. Words in the first column have to be matched with words in the second column. A valid solution to this question requires every word in the first column to be matched with only one word in the second column and vice-versa.

Input

First line contains a single integer T (1 <= T <= 1000) denoting the total number of test cases. Each test case contains a single integer N (1 <= N <= 1000000).

Output

For each test case, print a single integer the required number of ways modulo 1000000007

Example

Input:
3
1
2
7

Output:
0
1
1854