Background

This problem is an enhanced version of Luogu September Monthly Contest II & NR I. E. Heartbeat. The only difference is that the constraints are changed to $n \le 5 \times {10}^6$.

“From the clear beating sound, overlapping echoes and flowing longing are conveyed.

Let’s promise never to be apart again, and hope that no matter when, you will not be left lonely.”

When people are in love, their mood does not stay the same forever. Joy and sadness will become calm as time passes. What is most unforgettable is the feeling of “being moved,” the pleasant surprise from things never experienced before. Therefore, sometimes, losing some especially beautiful memories can instead make that thrilling feeling happen more often. But is it really worth losing those memories for that?

Problem Description

Herlde wants to explore the question above. She wants to do some statistics first, so she abstracts the problem.

For a sequence $p$ of length $l$, we 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 maximums).

Now, given $n, m$, find how many sequences $a$ of length $n$ with values in $[m,n]$ satisfy:

• There exists a permutation $p$ such that: let $P_i$ denote the sequence obtained from $p$ by removing $p_i$ (i.e. $[p_1,p_2,\dots,p_{i-1},p_{i+1},\dots,p_n]$), and $f(P_i)=a_i$.

The answer should be taken modulo $10^9+7$.

Input Format

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

Output Format

One line with one integer, representing the answer.

3 1

6

5 3

8

500000 100000

226048544

Hint

[Sample Explanation #2]

There are $8$ different possible $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 $1 \le m < n \le 5 \times {10}^6$.

Herlde successfully computed the number of different kinds of love. But she will only experience one of them.

Translated by ChatGPT 5