Informatica Online Judge

  타일채우기II(Small) [0694 / 02B6]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 279   Total Tried : 430


The Champion of this Problem (C++) : gs17016 - 0ms / 112byte
My Best Submission (C++) : N/A

[]

Background

자연수 n이 입력될 때, 2*n모양의 타일을 1*2, 1*1타일으로 채우는 경우의 수를 1,000,000으로 나눈 나머지를 구하여라.

(단, 모든 타일은 회전하여 배치할 수 있다.)

Input

첫 줄에 n이 입력된다.
(1<=n<=10,000,000)

Output

경우의 수를 1,000,000으로 나눈 나머지를 출력한다.

IO Example

입력1
1

출력1
2

입력2
5

출력2
228

입력3
100000

출력3
759185

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