P8554 Heartbeat

“The clear sound of a heartbeat carries overlapping echoes and flowing longing. Let’s promise never to be apart again, and hope that no matter when, you will not feel lonely.” When people are in love, their feelings do not stay the same. Joy and sadness will both fade into calm as time passes. What is most unforgettable is the feeling of “being moved,” the kind of surprise and happiness from things you have never experienced before. Therefore, sometimes, losing some especially beautiful memories can instead make that “heartbeat” feeling happen more often. But is it really worth losing those memories for it?

Helde wants to study the question above. She plans to collect some statistics first, so she abstracts the problem. For a sequence $p$ of length $l$, define the function: - $f(p)$ is the number of indices $1 \le i \le l$ such that $p_i = \max_{j=1}^i p_j$ (that is, the number of prefix maxima). Now, given $n, m$, compute how many sequences $a$ of length $n$ with values in $[m, n]$ satisfy the following condition: - There exists a permutation $p$ such that: let $P_i$ denote the sequence obtained from $p$ by removing $p_i$ (that is, $[p_1,p_2,\dots,p_{i-1},p_{i+1},\dots,p_n]$), and $f(P_i) = a_i$. Output the answer modulo $10^9+7$.

One line contains two positive integers $n, m$.

One line contains one number, the answer.

**[Sample Explanation #2]** There are the following $8$ different sequences $a$: 1. $\{4,4,4,4,4\}$, one corresponding $p$ is $\{1,2,3,4,5\}$. 2. $\{3,3,3,4,4\}$, one corresponding $p$ is $\{1,2,3,5,4\}$. 3. $\{3,3,4,4,3\}$, one corresponding $p$ is $\{1,2,4,3,5\}$. 4. $\{3,3,3,3,4\}$, one corresponding $p$ is $\{1,2,4,5,3\}$. 5. $\{3,4,4,3,3\}$, one corresponding $p$ is $\{1,3,2,4,5\}$. 6. $\{3,3,3,4,3\}$, one corresponding $p$ is $\{1,3,4,2,5\}$. 7. $\{4,4,3,3,3\}$, one corresponding $p$ is $\{2,1,3,4,5\}$. 8. $\{3,3,4,3,3\}$, one corresponding $p$ is $\{2,3,1,4,5\}$. --- **[Constraints]** For all testdata, 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 ID}&~~\bm{n\le} ~~&~~\bm{m\le}~~ &\textbf{Score}\cr\hline \textsf1 & 9 &1&8\cr\hline \textsf2 & 18&1&12 \cr\hline \textsf3 & 70&1&15\cr\hline \textsf4 & 70 &&24\cr\hline \textsf5 & 300&&18 \cr\hline \textsf6 & &&23\cr\hline\end{array} $$ If it is not written, then there is no special restriction. --- Helde successfully computed the number of different kinds of love. But she will only experience one of them. Translated by ChatGPT 5