시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 40 19 17 51.515%

문제

치삼이는 무한하게 연결되어있는 이진트리를 하나 가지고 있었다.

그러나 밤새 자던 사이에 누군가 치삼이의 이진트리의 간선을 모두 끊어버렸다..

치삼이는 이제 E개의 간선만이 남아 있을 뿐이다.

치삼이는 E개의 간선이라도 사용하여 하나의 이진트리를 다시 만들려 한다.

이진트리는 반드시 간선으로 이어져 있어야만 트리로 인정이 되며, 주어진 간선을 반드시 모두 사용해야만 한다.

이때, 치삼이를 도와 E개의 간선으로 만들 수 있는 이진트리의 경우의 수를 구하자.

입력

첫 번째 줄에 테스트케이스의 개수를 나타내는 T(1 ≤ T ≤ 100)가 주어진다.

두 번째 줄부터 각 테스트케이스마다 간선의 개수를 나타내는 E가 주어진다. (1 ≤ E ≤ 5,000)

출력

각 테스트 케이스에 대해 개수가 E인 간선으로 만들 수 있는 이진 트리의 개수를 1,000,000,007로 나눈 나머지를 출력하시오.

예제 입력 1

1
2

예제 출력 1

5

예제 입력 2

2
4
8

예제 출력 2

42
4862