궁전
시간 제한2초메모리 제한512 MB
N×N 체스판에 룩과 왕의 이동을 합한 궁성 기물 N개를 서로 공격하지 않게 놓는 경우의 수를 1,000,000,007로 나눈 나머지로 구합니다. 테스트 케이스는 최대 1,000,000개이고 N은 10,000,000 이하입니다.
문제
체스가 지겨워진 구사과는 새로운 체스 말을 만들었다.
새로 만든 체스말은 "궁전" 이다. 궁전은 룩의 이동 방법과 킹의 이동 방법을 모두 사용할 수 있다. 즉, 같은 행 또는 열에 있는 칸이나 인접한 네 방향과 대각선 네 방향으로 이동할 수 있다.
크기가 N×N인 체스판 위에 궁전 N개를 놓는 방법을 구하는 프로그램을 작성하시오. 체스판 위에 놓인 궁전은 서로 공격할 수 없어야 한다.
입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000,000)가 주어진다. 각 테스트 케이스는 한 줄에 하나씩 주어지며, 체스판의 크기 N(1 ≤ N ≤ 10,000,000)이 주어진다.
출력
각각의 테스트 케이스마다 궁전 N개를 놓는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.