시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB116715662.921%

문제

N개의 블록이 일렬로 놓여져 있습니다. 민호는 각각의 블록들을 빨, 주, 노, 초 네가지 색중 한가지 색으로 칠하려 합니다.

민호는 문득 빨간색으로 칠해진 블록의 개수와 노란색으로 칠해진 블록의 개수가 2로 나누어 떨어지게 칠하는 방법의 수가 몇 가지 인지 궁금해 졌습니다.

민호를 도와주는 프로그램을 작성해 봅시다.

입력

첫 번째 줄에 N (1 ≤ N ≤ 109)이 주어집니다.

출력

N개의 블록들을 모두 칠했을 때 빨간색과 노란색으로 칠해진 블록의 개수가 2로 나누어 떨어지게 칠하는 경우의 수를 출력하세요. 경우의 수가 매우 커질 수 있으므로 10,007로 나눈 나머지를 출력하세요.

예제 입력 1

1

예제 출력 1

2

예제 입력 2

2

예제 출력 2

6

출처

  • 문제의 오타를 찾은 사람: doju, jh05013
  • 어색한 표현을 찾은 사람: rdd6584