Count the number of labeled strongly connected digraphs with the given number of vertices.

Input Format
The first line contains , the number of queries.
Following are lines. Each line contains one integer , denoting the number of vertices.

Output Format
Output lines. Each line is the number of labeled strongly connected digraphs with vertices, modulo .

Constraints

Sample Input

5
1
2
3
4
1000

Sample Output

1
1
18
1606
871606913

Explanation

You can refer to oeis.