자기 서술 수열

자연수 $N$이 주어진다. 길이가 $N$인 수열 $A = (A_0, A_1, \ldots, A_{N-1})$이 $0 \le i < N$인 모든 $i$에서 다음을 만족하면 자기 서술 수열이라고 한다.

$A_i$는 수열 $A$ 안에 값 $i$가 등장하는 횟수와 같다.

길이가 $N$인 자기 서술 수열이 몇 개인지 세어라.

첫째 줄에 테스트 케이스의 수를 뜻하는 자연수 $T$가 주어진다. 이어지는 $T$개의 줄에는 수열의 길이 $N$ $(1 \le N \le 100)$이 한 줄에 하나씩 주어진다.

각 테스트 케이스마다 길이가 $N$인 자기 서술 수열의 개수를 1,000,000,007로 나눈 나머지를 한 줄에 출력한다.

$N = 5$이면 조건을 만족하는 수열은 $(2, 1, 2, 0, 0)$ 하나뿐이다. $N = 4$이면 $(2, 0, 2, 0)$과 $(1, 2, 1, 0)$ 두 개가 있다.