count-leaderboards-monk

You are about to organize a big programming competition. N competitors are registered for it. You know that you are going to divide all of them in some number of rooms. After the competition, each room will have its own leaderboard computed i.e. the order of competitors in that room based on their performance. You decided that after the competition, K random competitors will be awarded by lucky-one award. You will mark these lucky competitors with stars near their names on leaderboards. You set the scoring in such a way that there will be no draws between any players.

A global leaderboard is a set of leaderboards of all rooms after the competition, with exactly K lucky competitors marked with stars near their names.

You are interested in how many different global leaderboards exist.

Since the resulting number of global leaderboards can be very large, you are interested its value modulo 10^9 + 7

Input:

In the one and only line of input, there are two integers N and K, denoting the number of competitors registered for the contest and the number of competitors to be awarded by lucky-one award.

Output:

In one line, output the number of different global leaderboards.

Constraints:

1 ≤ N ≤ 1000
0 ≤ K ≤ N

SAMPLE INPUT
2 2

SAMPLE OUTPUT
3

Explanation

You can divide all competitors either in two rooms or place all of them in one room.

If you divide them into two rooms, each room will have exactly one competitor, so there is only one leaderboard possible for each such room.

If you divide them into one room, there are two possible leaderboards for that room - either the first players is better than the second, or the second is better than the first. 

At the end, you randomly award 2 competitors with the stars and since there are only 2 competitors, there is one way to do it in both above cases.

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions: