초콜릿과 왕 게임
시간 제한1초메모리 제한1024 MB
3 x N 초콜릿에서 킹이 왼쪽 위 칸에서 시작해 모든 칸을 한 번씩 밟고 오른쪽 아래 칸에 도달하는 경로의 수를 10^9로 나눈 나머지를 구한다.
문제
코코는 초콜릿과 체스 킹 1개를 가지고 "왕 게임"을 하려고 한다. 왕 게임은 초콜릿의 맨 왼쪽 위 칸에서 시작해서, 체스 킹의 이동 규칙에 따라 초콜릿의 모든 칸을 정확히 한 번씩 밟은 다음 맨 오른쪽 아래 칸에 도달하면 이기는 게임이다. 킹은 현재 칸에서 8방향으로 이웃한 칸으로 이동할 수 있으나, 초콜릿 밖으로는 이동할 수 없다.
코코는 왕 게임에서 이기는 방법의 수가 궁금해졌다. 코코의 궁금증을 해결해주자.
입력
첫 번째 줄에 정수 의 값이 주어진다.
출력
첫 번째 줄에 정답을 로 나눈 나머지를 출력한다.