Transformer Knight's Tour

시간 제한3초메모리 제한1024 MB

요약

4×N 격자의 왼쪽 위 칸에서 출발해 나이트와 퍼즈 이동을 번갈아 쓰며 모든 칸을 한 번씩 방문하고 제자리로 돌아오는 경로의 수를 1e9+7로 나눈 나머지를 구한다.

문제

크기가 $4\times N$ 인 격자판의 맨 왼쪽 위 칸에 트랜스포머 나이트가 하나 놓여 있다. 트랜스포머 나이트는 체스 나이트 또는 퍼즈(Ferz)처럼 이동할 수 있다.

나이트는 현재 자신이 있는 칸에서 가로로 2칸, 세로로 1칸 떨어진 칸으로 이동하거나 가로로 1칸, 세로로 2칸 떨어진 칸으로 이동할 수 있다.
퍼즈는 현재 자신이 있는 칸에서 가로로 1칸, 세로로 1칸 떨어진 칸으로 이동할 수 있다.

트랜스포머 나이트는 처음에 나이트처럼 이동하여, 나이트와 퍼즈의 이동 방식을 번갈아 가며 이동한다. 즉, 나이트 - 퍼즈 - 나이트 - 퍼즈 - …와 같이 이동한다.

트랜스포머 나이트를 이동하여 격자판의 모든 칸을 정확히 한 번씩 밟고 다시 출발점으로 돌아오는 경로의 수를 구하시오.

첫 번째 줄에 정수 $N$ 의 값이 주어진다.

첫 번째 줄에 문제의 답을 $1\\, 000\\, 000\\, 007$ 로 나눈 나머지를 출력한다. $1\\, 000\\, 000\\, 007$ 은 소수이다.