Problem Background

"The clear beating conveys, overlapping sounds and flowing thoughts.

Let's promise to never separate again, hoping to never leave you lonely."

In love, one's feelings do not remain constant, but joy and sorrow will fade over time. The most unforgettable are those "heartbeat" sensations, those unexpected joys from unexperienced moments. Therefore, sometimes, losing some particularly beautiful memories can actually increase the feeling of heartbeats. But is it really worth losing those memories for this?

Problem Description

Hilder wants to explore the above question, so she decides to start with some statistics by abstracting the problem.

For a sequence \( p \) of length \( l \), we define the function:

• \( f(p) \) represents the number of \( 1 \le i \le l \) such that \( p_i = \max_{j=1}^i p_j \) (i.e., the number of prefix maximums).

Given \( n, m \), we need to find how many sequences \( a \) of length \( n \) with values in the range \([m, n]\) satisfy the following condition:

• There exists a permutation \( p \) such that: let \( P_i \) represent the sequence \( p \) with \( p_i \) removed (i.e., \([p_1, p_2, \dots, p_{i-1}, p_{i+1}, \dots, p_n]\)), \( f(P_i) = a_i \).

The answer should be taken modulo \( 10^9 + 7 \).

Input Format

A single line containing two positive integers \( n, m \).

Output Format

A single line containing the answer.

Sample Input and Output

Sample Input #1

3 1

Sample Output #1

6

Sample Input #2

5 3

Sample Output #2

8

Sample Input #3

50 10

Sample Output #3

664411387

Notes

[Sample Explanation #2]

There are 8 different \( a \) sequences:

1. \(\{4, 4, 4, 4, 4\}\), corresponding to a permutation \( p \) such as: \(\{1, 2, 3, 4, 5\}\);
2. \(\{3, 3, 3, 4, 4\}\), corresponding to a permutation \( p \) such as: \(\{1, 2, 3, 5, 4\}\);
3. \(\{3, 3, 4, 4, 3\}\), corresponding to a permutation \( p \) such as: \(\{1, 2, 4, 3, 5\}\);
4. \(\{3, 3, 3, 3, 4\}\), corresponding to a permutation \( p \) such as: \(\{1, 2, 4, 5, 3\}\);
5. \(\{3, 4, 4, 3, 3\}\), corresponding to a permutation \( p \) such as: \(\{1, 3, 2, 4, 5\}\);
6. \(\{3, 3, 3, 4, 3\}\), corresponding to a permutation \( p \) such as: \(\{1, 3, 4, 2, 5\}\);
7. \(\{4, 4, 3, 3, 3\}\), corresponding to a permutation \( p \) such as: \(\{2, 1, 3, 4, 5\}\);
8. \(\{3, 3, 4, 3, 3\}\), corresponding to a permutation \( p \) such as: \(\{2, 3, 1, 4, 5\}\).

[Data Range]

For all data, it is guaranteed that \( 3 \le n \le 2000, 1 \le m \le n \).

$$ \def\arraystretch{1.5} \begin{array}{c|c|c|c}\hline \textbf{Subtask Number}&~~\bm{n\le} ~~&~~\bm{m\le}~~ &\textbf{Score}\cr\hline 1 & 9 &1&8\cr\hline 2 & 18&1&12 \cr\hline 3 & 70&1&15\cr\hline 4 & 70 &&24\cr\hline 5 & 300&&18 \cr\hline 6 & &&23\cr\hline\end{array} $$

No special restrictions if not mentioned.

Hilder successfully calculated the number of different love experiences. But she will only experience one of them.

见题面 Input 部分

见题面 Output 部分