Problem Background

This problem is an enhanced version of "Luogu September Monthly Contest II & NR I. E. Heartbeat", with the only difference being the data range changed to \( n \le 5 \times 10^6 \).

"The clear beating sound conveys, overlapping echoes and flowing thoughts.

Let's make a 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, the 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?

Problem Description

Hilder wants to explore the above question, so she first decides to do some statistics and abstracts 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 out 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 one number, representing 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

500000 100000

Sample Output #3

226048544

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 \( 1 \le m < n \le 5 \times 10^6 \).

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

见题面 Input 部分

见题面 Output 部分