선영이는 매우 긴 직선의 원점에 서 있다. 선영이는 왼쪽이나 오른쪽으로 한 번에 한 칸씩 이동할 수 있다.

2N번 움직여서 시작한 위치로 돌아오는 랜덤 걷기 문제의 경로의 수는 (\begin{pmatrix}  2N  \  N  \end{pmatrix}) 이다. 시작한 점으로 다시 이동해야 하기 때문에, 왼쪽으로 이동한 횟수와 오른쪽으로 이동한 횟수가 같아야 한다. 따라서, N번 오른쪽으로, N번 왼쪽으로 움직이면 되기 때문이다.

선영이는 위의 문제에서 음수 좌표로 이동할 수 있다. 음수 좌표로 이동할 수 없는 조건을 추가했을 때, 경로의 수를 구하는 프로그램을 작성하시오. 예를 들어, N = 1인 경우에 선영이는 0 → 1 → 0으로 이동할 수 있다. 하지만, 0 → -1 → 0 으로는 이동할 수 없다.

입력 형식

첫째 줄에 테스트 케이스의 개수 T ≤ 1000 가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, N (1 ≤ N ≤ 1,000,000)이 주어진다.

출력 형식

각 테스트 케이스 마다 음수 좌표를 방문하지 않고 시작점으로 도아오는 랜덤 걷기의 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

3
1
3
6

예제 출력

1
5
132