| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 182 | 98 | 77 | 62.602% |
N개의 블록이 일렬로 놓여져 있습니다. 민호는 각각의 블록들을 빨, 주, 노, 초 네가지 색중 한가지 색으로 칠하려 합니다.
민호는 문득 빨간색으로 칠해진 블록의 개수와 노란색으로 칠해진 블록의 개수가 2로 나누어 떨어지게 칠하는 방법의 수가 몇 가지 인지 궁금해 졌습니다.
민호를 도와주는 프로그램을 작성해 봅시다.
첫 번째 줄에 N (1 ≤ N ≤ 109)이 주어집니다.
N개의 블록들을 모두 칠했을 때 빨간색과 노란색으로 칠해진 블록의 개수가 2로 나누어 떨어지게 칠하는 경우의 수를 출력하세요. 경우의 수가 매우 커질 수 있으므로 10,007로 나눈 나머지를 출력하세요.
1
2
2
6