Self-Describing Sequences

Time limit1sMemory limit256 MB

Summary

Count length-N sequences where each entry A[i] equals the number of times i appears in the sequence.

Level: Hard8 of 10
Topics: Math, Combinatorics, Backtracking
Solved: No attempts yet

Problem

You are given a natural number $N$ . A sequence $A = (A_0, A_1, \ldots, A_{N-1})$ of length $N$ is self-describing when the following holds for every $i$ with $0 \le i < N$ .

$A_i$ equals the number of times the value $i$ occurs in $A$ .

Count the self-describing sequences of length $N$ .

Input

The first line contains a natural number $T$ , the number of test cases. Each of the next $T$ lines contains one sequence length $N$ $(1 \le N \le 100)$ .

Output

For each test case, print on one line the number of self-describing sequences of length $N$ , taken modulo 1,000,000,007.

Hint

For $N = 5$ the only sequence that satisfies the condition is $(2, 1, 2, 0, 0)$ . For $N = 4$ there are two, $(2, 0, 2, 0)$ and $(1, 2, 1, 0)$ .

Examples6

Example 1
Input
```
3
2
5
4
```
Expected output
```
0
1
2
```
Example 2
Input
```
1
1
```
Expected output
```
0
```
Example 3
Input
```
1
3
```
Expected output
```
0
```
Example 4
Input
```
1
7
```
Expected output
```
1
```
Example 5
Input
```
1
100
```
Expected output
```
1
```

Example 6

Input

Expected output