문제 번호 B: 타일 채우기II

문제 번호 B: 타일 채우기II

시간제한: 1 Sec  메모리제한: 128 MB
제출: 451  푼문제: 118
[제출][채점상황][게시판]

문제설명

2*N 크기의 판이 있다. 이 판에 2*1, 2*2 짜리 타일들을 깔려고 한다. 타일을 깔 수 있는 경우의 수를 구하시오.

입력

첫 번째 줄에 N(1<=N<=100,000)이 주어진다.

출력

첫 번째 줄에 가능한 경우의 수를 100,000,007로 나눈 나머지를 출력하시오.

입력예시

2

출력예시

3

도움말

[제출][채점상황]