Informatica Online Judge

  현우의 타일채우기 [1985 / 07C1]

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


The Champion of this Problem (C++) : tlsdydaud1 - 10ms / 311byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16109]

Background

2*n타일을 1*2, 1*1타일로 채우는 경우의 수를 구한 현우는 3*n타일에 도전했다.
자연수 n이 입력될 때, 3*n모양의 타일을 1*2, 1*1타일로 채우는 경우의 수를 10억 7로 나눈 나머지를 구하여라.

Input

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

Output

경우의 수를 10억 7로 나눈 나머지를 출력한다.

IO Example

입력1
1

출력1
3

입력2
2

출력2
22

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