Adnan And Chess Tournament

adnan_toky Criterion 2022 Round 17
Limits 1s, 256 MB

Adnan is going to organize a chess tournament. He has invited nn 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 109+710^9+7.

A game between two players ii and jj (ij)(i\neq j) is denoted by (i,j)(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 s1s_1 and the set of selected games of the second way is s2s_2 then two ways are different if s1s2s_1 \neq s_2. The game denoted by (i,j)(i, j) and (j,i)(j, i) are same.

Input

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

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

Output

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

Sample

InputOutput
5
1
2
3
5
10
0
1
4
768
11652982

For, n=3n=3, there are 44 valid ways:

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

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

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

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

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


Submit

Login to submit.

Statistics

80% Solution Ratio
NirjhorEarliest, 1M ago
NirjhorFastest, 0.0s
ash_98Lightest, 221 kB
NirjhorShortest, 962B
Toph uses cookies. By continuing you agree to our Cookie Policy.