C2. Cycles (Difficult)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The only difference between this problem and the easy version is the value of $$$n$$$.

Given a permutation $$$P$$$ of $$$n$$$ elements, let $$$G$$$ be a directed graph with $$$n$$$ vertices, where there is a directed edge from $$$i$$$ to $$$P_i$$$ for every $$$1 \leq i \leq n$$$.

Determine the number of permutations $$$P$$$ such that the graph $$$G$$$ induced by the permutation contains at least one cycle of size greater than or equal to $$$T$$$, where $$$T$$$ is a given integer ($$$1 \leq T \leq n$$$).

Since this number can be large, print the answer modulo $$$10^9 + 7$$$.

Input

The input consists of two integers $$$n$$$ and $$$T$$$ in that order.

It is guaranteed that $$$1 \leq T \leq n \leq 10^6$$$.

Output

Print the number of permutations with at least one cycle of size $$$T$$$ or more. Since this number can be large, print the answer modulo $$$10^9 + 7$$$.

Examples
Input
5 2
Output
119
Input
5 4
Output
54
Input
10 4
Output
3457224