10220번 - Self Representing Seq

문제

자연수 N이 주어질 때 다음과 같은 길이 N인 수열 A의 개수를 구하여라

A_i = A에서 i가 등장하는 횟수 (0 ≤ i < N)

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스에는 수열의 길이를 의미하는 하나의 자연수 N (1 ≤ N ≤ 100)이 입력으로 주어진다.

출력

각 테스트 케이스마다 한 줄에 가능한 A의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

제한

힌트

두 번째 예제의 경우 가능한 A는 (2,1,2,0,0) 한 개만 존재한다.

세 번째 예제의 경우 가능한 A는 (2,0,2,0), (1,2,1,0) 두 개 존재한다.