Informatica Online Judge

  코드업 블럭채우기 6 [1658 / 067A]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 113   Total Tried : 114


The Champion of this Problem (C++) : gs14117 - ms / 235byte
My Best Submission (C++) : N/A

[CODEUP]

Background

$2×1$과 $1×1$의 사각형 블럭을 이용하여 $2×n$ 크기의 직사각형 모양으로 채우려고 한다.



가능한 방법의 수를 구하여라. 사각형 블럭은 무한정 있다고 가정한다.

이 때 숫자가 커질 수 있으므로 $100,007$로 나눈 나머지를 출력하시오.

Input

첫 줄에 $n$이 입력된다.

[입력값의 정의역]

$1 \leq n \leq 100,000$

Output

$2×n$의 직사각형을 채울 수 있는 방법의 수에 $100,007$로 나눈 나머지를 출력하시오.

IO Example

입력
2

출력
7

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]