시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 11 10 5 100.000%

문제

체스가 지겨워진 구사과는 새로운 체스 말을 만들었다.

새로 만든 체스말은 "궁전" 이다. 궁전은 룩의 이동 방법과 킹의 이동 방법을 모두 사용할 수 있다. 즉, 같은 행 또는 열에 있는 칸이나 인접한 네 방향과 대각선 네 방향으로 이동할 수 있다.

크기가 N×N인 체스판 위에 궁전 N개를 놓는 방법을 구하는 프로그램을 작성하시오. 체스판 위에 놓인 궁전은 서로 공격할 수 없어야 한다.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000,000)가 주어진다. 각 테스트 케이스는 한 줄에 하나씩 주어지며, 체스판의 크기 N(1 ≤ N ≤ 10,000,000)이 주어진다.

출력

각각의 테스트 케이스마다 궁전 N개를 놓는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

8
1
2
3
7
10
1000
10000
9999999

예제 출력 1

1
0
0
646
479306
711794305
450342414
838796194

출처