Informatica Online Judge

  극장 좌석 배치 (L) [1403 / 057B]

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


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

[JKJeong 2015]

Background

GSHS극장에는 1열로 좌석이 배치되어 있다.

일단 n개의 좌석이 있으며, m명의 사람들이 영화를 보러 왔다.

이 사람들이 각각의 자리에 앉으려고 한다.

지정석은 없으며 아무 자리에나 앉을 수 있다.

단, 연속으로 2명을 초과하는 인원이 앉을 수 없다.

예를 들어 4자리가 있고 3명이 앉으려면 다음과 같은 배치가 가능하다.

1 1 0 1
1 0 1 1

이 배치는 가능하다. 최대 2명까지 연속해서 앉았기 때문이다.

하지만

1 1 1 0

과 같은 배치는 불가능하다. 연속으로 2명을 초과해서 앉았기 때문이다.

좌석의 수와 영화를 보려는 관객의 수가 주어질 때 앉을 수 있는 서로 다른 배치를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 좌석의 수 n과 사람의 수 m이 공백으로 구분되어 입력된다.

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

Output

앉을 수 있는 서로 다른 경우의 수를 출력한다.

단, 경우의 수가 너무 커질 수 있으니 10억 7로 나눈 나머지를 출력한다.

IO Example

입력
4 3

출력
2

* 설명 : 위에서 설명한 경우와 같은 2가지 뿐이다.

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