25799번 - 초콜릿과 왕 게임

코코는 $3 \times N$ 초콜릿과 체스 킹 1개를 가지고 "왕 게임"을 하려고 한다. 왕 게임은 초콜릿의 맨 왼쪽 위 칸에서 시작해서, 체스 킹의 이동 규칙에 따라 초콜릿의 모든 칸을 정확히 한 번씩 밟은 다음 맨 오른쪽 아래 칸에 도달하면 이기는 게임이다. 킹은 현재 칸에서 8방향으로 이웃한 칸으로 이동할 수 있으나, 초콜릿 밖으로는 이동할 수 없다.

코코는 왕 게임에서 이기는 방법의 수가 궁금해졌다. 코코의 궁금증을 해결해주자.

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

첫 번째 줄에 정답을 $10^9$로 나눈 나머지를 출력한다.

• $1 \le N \le 10^3$