블록 칠하기

N개의 블록이 일렬로 놓여 있다. 민호는 블록 하나하나를 빨강, 주황, 노랑, 초록 네 색 중 한 색으로 칠한다.

민호는 빨강으로 칠한 블록의 개수와 노랑으로 칠한 블록의 개수가 둘 다 2로 나누어떨어지는 칠하기가 몇 가지인지 알고 싶다. 블록의 자리는 고정되어 있으므로, 한 자리라도 색이 다르면 서로 다른 칠하기로 센다. 개수가 0인 경우도 2로 나누어떨어지는 것으로 본다.

N을 읽어 그 칠하기의 수를 구하는 프로그램을 작성하라.

첫째 줄에 N이 주어진다. ($1 \le N \le 10^9$)

빨강으로 칠한 블록의 개수와 노랑으로 칠한 블록의 개수가 모두 2로 나누어떨어지는 칠하기의 수를 10007로 나눈 나머지를 출력한다.