크기가 \(2 \times N\)인 직사각형을 다음과 같은 타일로 채우려고 한다.

• 크기가 \(2 \times 1\)인 타일
• 크기가 \(2 \times 2\)인 타일

각 타일은 회전하여 사용할 수 있으며, 같은 종류의 타일을 여러 번 사용할 수 있다.

타일을 겹치거나 직사각형의 바깥으로 나가게 놓을 수 없으며, 직사각형의 모든 칸을 빈틈없이 채워야 한다.

아래 그림은 사용할 수 있는 타일과 비어 있는 \(2 \times 5\) 직사각형을 나타낸다. 타일 내부의 선은 각 칸의 경계를 나타낸다.

\(2 \times N\) 직사각형을 채우는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 직사각형의 가로 길이 \(N\)이 주어진다.

출력

첫째 줄에 \(2 \times N\) 직사각형을 채우는 방법의 수를 \(100,007\)로 나눈 나머지를 출력한다.

제한 사항

• \(1 \le N \le 100,000\)

예제 입력 1

2

예제 출력 1

3

예제 입력 2

5

예제 출력 2

21