Informatica Online Judge

  코드업 블럭채우기 2 [1654 / 0676]

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


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

[CODEUP]

Background

다음과 같은 "ㄱ"자 모양의 블럭이 있다. 이 블럭을 이용하여 $2×n$ 크기의 직사각형 모양으로 채우려고 한다.



가능한 방법의 수를 구하여라. "ㄱ"자 블럭은 무한정 있다고 가정한다.

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

Input

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

[입력값의 정의역]

$1 \leq n \leq 100,000$

Output

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

IO Example

입력
3

출력
2

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