Informatica Online Judge

  자연탐사 [1081 / 0439]

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


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

[JeongHJ]

Background

병찬이는 koi 동아리의 학생들과 자연탐사를 떠났다. 목적지에 도작하여 숙소를 살펴보던 병찬이는 깜짝 놀랐다.

예약된 방의 수가 생각보다 적었다는 사실을 발견하였기 때문이다. 이제 n명의 학생들을 k개의 방에 나누어 배치해야 하는 문제가 발생하게 된 것이다.

이 사실을 안 모든 동아리 부원들은 병찬이에게 어떻게 할거냐고 난리법석이 났다. 어떻게 이 위기를 해결해야 하는지 머리가 아프다.

병찬을 도와 n명의 학생을 k개의 방으로 나누어 배치하는 가능한 경우의 수를 찾아 주기 바란다.

당연히 모든 방에는 적어도 한 명은 들어가야 하며, 방은 구분되지 않는다.

학생 A, B, C가 있고 방이 2개 있을 때,

{A, B}, {C}와 {C}, {A,B}는 같은 경우이나, {A], {B, C}와 {B}, {A, C}는 다른 경우이다.

* 이 문제는 recursion연습문제이므로 반복문을 사용할 수 없습니다. 재귀함수로 해결하시기 바랍니다.

Input

두 정수 n, k가 공백으로 구분되어 입력된다. (1<=k<=n<=1000)

Output

n명의 학생들을 k개의 방에 나누어 배치하는 가능한 모든 경우의 수를 1,000,000,007(10억 7)로 나눈 값을 출력한다.출력한다.

IO Example

입력
7 2

출력
63

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