Solve the programming task below in a Python markdown code block.
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.