Problem Background

Little W has opened a new restaurant at home.

Problem Description

This restaurant offers $n$ special dishes, numbered from $1$ to $n$.

One day, $k$ customers came to the restaurant without deciding what to eat. Little W suggested that each person first randomly select a number $r$ from $1$ to $n$ with equal probability, and then randomly select a number $l$ from $1$ to $r$ with equal probability. The person would then order the dishes numbered between $l$ and $r$ (inclusive).

Following Little W's advice, the customers did as instructed. After all the customers had placed their orders, Little W noticed that no two people had ordered the same dish, meaning he only needed to prepare each dish at most once! To prove how lucky he was, he turned to you, a programmer, to help him calculate the probability of this happening.

Input Format

Two integers $n$ and $k$, as described in the problem statement.

Output Format

An integer $p$, representing the result of the probability modulo $10^9+7$.

Sample Input and Output

Sample Input #1

10 1

Sample Output #1

1

Sample Input #2

2 2

Sample Output #2

250000002

Notes

Sample Explanation:
- Sample #1: Since there is only one guest, there will never be two people ordering the same dish, so the probability is $1$.
- Sample #2: The probability that each guest orders only dish #1 is $\frac{1}{2}$, only dish #2 is $\frac{1}{4}$, and both dishes is $\frac{1}{4}$. The probability that two guests do not order the same dish, i.e., one orders only dish #1 and the other only dish #2, is $\frac{1}{4} \times \frac{1}{2} + \frac{1}{2} \times \frac{1}{4} = \frac{1}{4}$, which modulo $10^9+7$ is $250000002$.

Hint: If you do not know how to take the modulo of a rational number, please refer to P2613.

Data Range

• For $10\%$ of the data, $k = 1$.
• For another $10\%$ of the data, $1 \le k \le n \le 5$.
• For another $20\%$ of the data, $1 \le k \le 3$.
• For another $30\%$ of the data, $1 \le k \le n \le 10^3$.
• For all data, $1 \le k \le n \le 10^8$.

见题面 Input 部分

见题面 Output 部分