Adnan And Chess Tournament

Limits 1s, 256 MB

Adnan is going to organize a chess tournament. He has invited $n$ players to participate. Each pair of players will play at most one game against each other. All the players will be happy if everyone can participate in at least one game. You want to arrange some games such that everyone becomes happy. Can you help him to calculate the number of ways to select the games? Output the answer modulo $10^9+7$ .

A game between two players $i$ and $j$ $(i\neq j)$ is denoted by $(i, j)$ . Two ways of selecting the games are different if they differ in at least one game. Formally, if the set of selected games of the first way is $s_1$ and the set of selected games of the second way is $s_2$ then two ways are different if $s_1 \neq s_2$ . The game denoted by $(i, j)$ and $(j, i)$ are same.

Input

The first line of input contains a single integer $t~ (1\leq t \leq 5000)$ $-$ the number of test cases.

Each of the next $t$ lines contains a single integer $n ~ (1\leq n \leq 5000)$ $-$ the number of invited players.

Output

For each test case, print the number of ways modulo $10^9+7$ in a single line.

Sample

Input	Output
5 1 2 3 5 10	0 1 4 768 11652982
For, $n=3$ , there are $4$ valid ways: $\{(1, 2), (1, 3)\}$ $\{(1, 2), (2, 3)\}$ $\{(1, 3), (2, 3)\}$ $\{(1, 2), (1, 3), (2, 3)\}$ Here, all the $4$ sets are different and everyone participated in at least one game in each of the $4$ ways of arrangement.

Input

Output

For, $n=3$ , there are $4$ valid ways:

$\{(1, 2), (1, 3)\}$

$\{(1, 2), (2, 3)\}$

$\{(1, 3), (2, 3)\}$

$\{(1, 2), (1, 3), (2, 3)\}$

Here, all the $4$ sets are different and everyone participated in at least one game in each of the $4$ ways of arrangement.