Informatica Online Judge

  기차 여행 (Small) [1178 / 049A]

Time Limit(Test case) : 5000 (ms)
Number of users who solved : 15   Total Tried : 90


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (31st 이의민)]

Background

경곽이는 서울에서 부산까지 가기 위해 총 N+1개의 객실을 가진 열차 X에 탑승하였다.

그런데 열차 X가 출발하기 위해서는 몇 가지 조건을 만족시켜야 한다고 한다.

만약 한 객실에 사람이 아무도 타지 않거나 N명보다 많은 사람이 타게 된다면 열차는 출발하지 않는다.

또한 사람이 한 명만 탄 객실은 항상 짝수개씩 연달아 존재해야만 한다.

마지막으로 임의의 M 번째 객실에 탄 사람이 M+1명을 초과하면 열차는 출발하지 않는다고 하자. (단 M은 1이상 N+1이하인 정수)

이 때 경곽이가 무사히 부산에 갈 수 있는 경우의 수는 총 몇가지일까?

(총 탑승객의 인원수는 제한이 없다.)

Input

N이 주어진다.

[입력값의 정의역]
N <= 1,000

[Sub-task Info]
#1 : N=1,2,3,4,5
#2 : N은 1000이하

Output

조건을 만족하는 가능한 경우의 수를 100,000,007으로 나눈 나머지를 출력한다.

IO Example

입력 1
5

출력 1
771

입력 2
1

출력 2
1

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