Informatica Online Judge

  준규의 타일채우기 (Small) [1946 / 079A]

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


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

[koistudy.net (34th 장준규)]
Writer ID : [gs15094]

Background

경곽이는 koistudy.net에있는 수많은 타일 채우기 문제들을 풀어왔다.

하지만 경곽이는 아직 배가 고프다.

사실 경곽이가 타일 채우기 문제를 많이 푼 이유는
경곽이는 사각형을 아주 좋아하기 때문이다.^^

다다익선! 타일의 개수가 많을수록 경곽이는 기뻐한다.

그래서 경곽이는 3*n짜리 타일을 3*1타일과 1*3타일만을 이용하여 채우려고 한다.

이 때, 경곽이는 n을 무진장 크게 하여 10000000000까지 해보려고 한다.

이 때, 3*n짜리 타일을 채울 수 있는 서로 다른 가지수를 구해라.

단, 경우의 수가 너무 많아질 수 있으므로 100000007로 나눈 가지수를 출력한다.

Input

첫째줄에 타일의 길이 n이 주어진다.

[Sub-Task Info]
1<= n <=100,000,000(small)
1<= n <=1,000,000,000,000(large)

Output

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

IO Example

입력
3

출력
2

가로로 세개, 세로로 세개 나열하는 방법 두가지 뿐이다.

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