시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 64 MB | 828 | 271 | 198 | 34.315% |
선영이는 매우 긴 직선의 원점에 서 있다. 선영이는 왼쪽이나 오른쪽으로 한 번에 한 칸씩 이동할 수 있다.
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