Informatica Online Judge

  보드 게임 [1068 / 042C]

Time Limit(Test case) : 100(ms)
Number of users who solved : 30   Total Tried : 338


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

[JKJeong 2014]

Background

경곽이는 간단한 보드게임을 진행한다.

이 게임은 주사위 대신 아래 그림과 같이 1~3까지의 값을 가지는 룰렛을 돌려서 말을 전진시킨다.





게임은 그림과 출발점에서 출발하여 도착점까지 이동하며, 출발점을 제외하고 도착점까지 모두 n개의 칸이 선형으로 구성되어 있다.





경곽이가 출발점에서 룰렛을 돌려 게임을 진행한다.

경곽이는 1, 2, 3이 나오는 각 경우에 따라 말을 이동시킨다. 그리고 경곽이가 미자막 도착점에 도착하면 게임은 성공으로 종료된다.

만약 도착점을 넘어가면 게임은 실패하게 된다.

경곽이가 게임을 성공으로 종료하는 서로 다른 경우의 수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 게임판의 크기 N이 입력된다.

[입력값의 정의역]
0 <= N <= 2,100,000,000


[Sub-Task Info]
#1 : N <= 1000
#2 : 추가제한 조건은 없다.

Output

경곽이가 게임을 성공으로 마치는 경우의 수를 출력한다.
단, 경우의 수가 너무 크기 때문에 100,000,007로 나눈 나머지를 출력한다.

IO Example

입력
4

출력
7

* 설명 : 다음과 같이 모두 7가지 경우가 있다.

- 1 1 1 1
- 1 1 2
- 1 2 1
- 2 1 1
- 2 2
- 1 3
- 3 1

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