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

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

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

입력 형식

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

출력 형식

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

예제 입력 1

1

예제 출력 1

2

예제 입력 2

2

예제 출력 2

6