\(2 \times N\) 크기의 직사각형을 다음 타일로 빈틈없이 채우려고 한다.

• \(1 \times 1\) 타일
• \(2 \times 1\) 타일
• \(2 \times 2\) 타일

타일은 회전하여 사용할 수 있다. 따라서 \(2 \times 1\) 타일을 회전한 \(1 \times 2\) 타일도 사용할 수 있다. 각 종류의 타일은 필요한 만큼 사용할 수 있다.

타일을 겹치거나 직사각형 밖으로 나오게 놓을 수 없다. 타일의 종류와 배치가 하나라도 다르면 서로 다른 방법으로 센다.

\(2 \times N\) 직사각형을 채우는 서로 다른 방법의 수를 구하여라.

입력

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

출력

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

제한 사항

• \(1 \le N \le 100,000\)
• 입력으로 주어지는 값은 정수이다.

예제 입력 1

1

예제 출력 1

2

\(2 \times 1\) 직사각형은 세로 \(2 \times 1\) 타일 하나 또는 \(1 \times 1\) 타일 두 개로 채울 수 있다.

예제 입력 2

2

예제 출력 2

8