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