18132번 - 내 이진트리를 돌려줘!!!

이진 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리이다.

치삼이는 무한하게 연결되어있는 이진 트리를 하나 가지고 있었다. 그러나 밤새 자던 사이에 누군가 치삼이의 이진 트리의 모든 정점과 간선을 분리한 후 E개를 제외한 모든 간선을 훔쳐갔다. 치삼이는 이제 무수히 많은 정점과 E개의 간선만이 남아 있을 뿐이다. 치삼이는 E개의 간선이라도 사용하여 하나의 이진 트리를 다시 만들려 한다. 이진 트리를 만들 때는 E개의 간선을 모두 사용하여 정점들을 연결해야 하고 이진 트리를 완성하고 남은 정점들은 버린다.

서로 대칭 관계에 있는 두 트리는 서로 다른 경우라고 했을 때, 치삼이를 도와 E개의 간선으로 만들 수 있는 이진 트리의 경우의 수를 구하자.

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

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

각 테스트 케이스에 대해 이진 트리의 경우의 수를 1,000,000,007로 나눈 나머지를 출력하시오.