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

Input Format

The first line contains $\mathbf{T}$, the number of queries.

Following are $\mathbf{T}$ lines. Each line contains one integer $N$, denoting the number of vertices.

Output Format

Output $\mathbf{T}$ lines. Each line is the number of labeled strongly connected digraphs with $N$ vertices, modulo $(10^9+7)$.

Constraints

$1\leq T\leq1000$

$1\leq N\leq1000$

Sample Input

5
1
2
3
4
1000

Sample Output

1
1
18
1606
871606913

Explanation

You can refer to oeis.

见题面

见题面