시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 146 43 35 42.169%

문제

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

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로 나눈 나머지를 출력한다.

예제 입력 1

3
1
3
6

예제 출력 1

1
5
132
W3sicHJvYmxlbV9pZCI6IjkzNDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI3OWNcdWIzNjQgXHVhYzc3XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViOWU0XHVjNmIwIFx1YWUzNCBcdWM5YzFcdWMxMjBcdWM3NTggXHVjNmQwXHVjODEwXHVjNWQwIFx1YzExYyBcdWM3ODhcdWIyZTQuIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM2N2NcdWNhYmRcdWM3NzRcdWIwOTggXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHVkNTVjIFx1Y2U3OFx1YzUyOSBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Mk5cdWJjODggXHVjNmMwXHVjOWMxXHVjNWVjXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWM3MDRcdWNlNThcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjI0XHViMjk0IFx1Yjc5Y1x1YjM2NCBcdWFjNzdcdWFlMzAgXHViYjM4XHVjODFjXHVjNzU4IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWMyMThcdWIyOTQgXFwoXFxiZWdpbntwbWF0cml4fSAmbmJzcDsyTiAmbmJzcDtcXFxcICZuYnNwO04gJm5ic3A7XFxlbmR7cG1hdHJpeH1cXCkgXHVjNzc0XHViMmU0LiBcdWMyZGNcdWM3OTFcdWQ1NWMgXHVjODEwXHVjNzNjXHViODVjIFx1YjJlNFx1YzJkYyBcdWM3NzRcdWIzZDlcdWQ1NzRcdWM1N2MgXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNjdjXHVjYWJkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWQ2OWZcdWMyMThcdWM2NDAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWQ2OWZcdWMyMThcdWFjMDAgXHVhYzE5XHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBOXHViYzg4IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YywgTlx1YmM4OCBcdWM2N2NcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0IFx1YjQxOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM3MDRcdWM3NTggXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1Yzc0Y1x1YzIxOCBcdWM4OGNcdWQ0NWNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc0Y1x1YzIxOCBcdWM4OGNcdWQ0NWNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVjODcwXHVhYzc0XHVjNzQ0IFx1Y2Q5NFx1YWMwMFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIE4gPSAxXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgMCAmcmFycjsgMSAmcmFycjsgMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCAwICZyYXJyOyAtMSAmcmFycjsgMCBcdWM3M2NcdWI4NWNcdWIyOTQgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgJmxlOyAxMDAwIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgTiAoMSAmbGU7IE4gJmxlOyAxLDAwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQgXHVjNzRjXHVjMjE4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWJjMjlcdWJiMzhcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YzJkY1x1Yzc5MVx1YzgxMFx1YzczY1x1Yjg1YyBcdWIzYzRcdWM1NDRcdWM2MjRcdWIyOTQgXHViNzljXHViMzY0IFx1YWM3N1x1YWUzMFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWM3NTggXHVjMjE4XHViOTdjIDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTM0MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJhbmRvbVx1MDBhMFdhbGtzIiwiZGVzY3JpcHRpb24iOiI8cD4mbGRxdW87VGhvcmZ1biBDb21wYW55IExpbWl0ZWQmcmRxdW87IGFrYSAmbGRxdW87dGhvcmZ1bi5jb20mcmRxdW87LCBhIHNvY2lhbCBuZXR3b3JrIGZvciBibG9nZ2VyLCB3cml0ZXIgYW5kIHJlYWRlciwgZm91bmRlZCBieSBmb3VyIG5ldyBncmFkdWF0ZWQuIE9uZSBvZiB0aGVtIGlzIHBhc3Npb24gaW4gY29tcHV0YXRpb25hbCBwcm9ibGVtcy4gT25lIGRheSBoZSBmb3VuZCBzb21ldGhpbmcgdmVyeSBpbnRlcmVzdGluZyBiZWNhdXNlLCBpdCBpcyBhIHNvbHV0aW9uIG9mIHZhcmlvdXMgcHJvYmxlbXMgYW5kICZsZHF1bztSYW5kb20gV2Fsa3MmcmRxdW87IGlzIG9uZSBvZiB0aGVtLiBHaXZlbiBhIG9uZSBkaW1lbnNpb25hbCBsaW5lIGFuZCB5b3Ugc3RhbmQgYXQgdGhlIG9yaWdpbmFsIHBvaW50IChwb3NpdGlvbiAwKS4gQXQgZWFjaCBzdGVwIHlvdSBjYW4gd2FsayBlaXRoZXIgbGVmdCBvciByaWdodCBmb3IgdW5pdCBsZW5ndGguPFwvcD5cclxuXHJcbjxwPkZpcnN0LCBsZXQgdXMgaGF2ZSBhIGxvb2sgYXQgYSBiYXNpYyB2ZXJzaW9uIG9mIHRoZSBwcm9ibGVtLiBZb3UgY2FuIHdhbGsgd2hhdGV2ZXIgeW91IHdhbnQgZm9yIDJOIHN0ZXBzIGJ1dCwgeW91IG11c3QgZW5kIGF0IHRoZSBvcmlnaW5hbCBwb2ludC4gSG93IG1hbnkgZGlmZmVyZW50IHBhdGhzIHRoYXQgeW91IGNhbiB3YWxrPyBUaGUgc29sdXRpb24gaXMgdmVyeSBzaW1wbGUuIFlvdSBzdGFydCBhbmQgZW5kIGF0IHRoZSBzYW1lIHBvaW50LCBpdCBtZWFucyB0aGF0IHlvdSBtdXN0IHRha2UgdGhlIHNhbWUgbnVtYmVyIG9mIGxlZnQgYW5kIHJpZ2h0IHN0ZXAuIENob29zaW5nIE4gZm9yIHRoZSByaWdodCBhbmQgdGhlIG90aGVyIE4gZm9yIHRoZSBsZWZ0IGZyb20gMk4gc3RlcHMgaXMgZXF1YWwgdG8gXFwoXFxiZWdpbntwbWF0cml4fSAmbmJzcDsyTiAmbmJzcDtcXFxcICZuYnNwO04gJm5ic3A7XFxlbmR7cG1hdHJpeH1cXCkuPFwvcD5cclxuXHJcbjxwPiZsZHF1bztSYW5kb20gV2Fsa3MmcmRxdW87IHByb2JsZW0gaXMgc2ltaWxhciB0byB0aGUgYmFzaWMgcHJvYmxlbS4gSG93ZXZlciwgZHVyaW5nIHRoZSB3YWxrcyB5b3UgbXVzdCBub3Qgd2FsayBpbnRvIG5lZ2F0aXZlIGludGVnZXJzLiBGb3IgZXhhbXBsZSwgaWYgTiA9IDEgeW91IGNhbiB3YWxrIG9uIHRoZSBwYXRoIDAgJnJhcnI7IDEgJnJhcnI7IDAgYnV0IHlvdSBjYW4mcnNxdW87dCB3YWxrIG9uIHBhdGggMCAmcmFycjsgLTEgJnJhcnI7IDAuIFlvdSB0YXNrIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBjb21wdXRlIHRoZSBudW1iZXIgb2YgcGF0aCB0aGF0IGZvbGxvdyB0aGUgYWJvdmUgcnVsZXMuIEluIGFkZGl0aW9uLCB0aGUgcmVzdWx0IG1heSBiZSB2ZXJ5IGxhcmdlLiBTbywgcHJpbnQgdGhlIHJlc3VsdCBtb2R1bG8gYnkgMSAwMDAgMDAwIDAwNyAoUHJpbWUgbnVtYmVyKS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgaXMgYSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUICZsZTsgMSAwMDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggdGVzdCBjYXNlIGlzIGEgbGluZSBjb250YWluIGFuIGludGVnZXJzIE4gKDEgJmxlOyBOICZsZTsgMSAwMDAgMDAwKSZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgZGlzcGxheSBhbiBpbnRlZ2VyIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBwYXRocyB0aGF0IHlvdSBjYW4gd2FsayBtb2R1bG8gYnkgMSAwMDAgMDAwIDAwNyZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==