세로 2, 가로 n인 직사각형 판을 세 종류의 타일 — 1×2(세로), 2×1(가로), 2×2(정사각) — 로 빈틈도 겹침도 없이 채우려 한다. 가능한 채우는 방법이 모두 몇 가지인지 구하는 프로그램을 작성하라.

아래 그림은 2×17 직사각형을 채운 한 가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

채우는 방법의 수를 10,007로 나눈 나머지를 첫째 줄에 출력한다.

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

예제 입력 3

12

예제 출력 3

2731