| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 219 | 115 | 86 | 51.190% |
체스가 지겨워진 구사과는 새로운 체스 말을 만들었다.
새로 만든 체스말은 "궁전" 이다. 궁전은 룩의 이동 방법과 킹의 이동 방법을 모두 사용할 수 있다. 즉, 같은 행 또는 열에 있는 칸이나 인접한 네 방향과 대각선 네 방향으로 이동할 수 있다.
크기가 N×N인 체스판 위에 궁전 N개를 놓는 방법을 구하는 프로그램을 작성하시오. 체스판 위에 놓인 궁전은 서로 공격할 수 없어야 한다.
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000,000)가 주어진다. 각 테스트 케이스는 한 줄에 하나씩 주어지며, 체스판의 크기 N(1 ≤ N ≤ 10,000,000)이 주어진다.
각각의 테스트 케이스마다 궁전 N개를 놓는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.
8 1 2 3 7 10 1000 10000 9999999
1 0 0 646 479306 711794305 450342414 838796194