K-minsum of Permutations

Time limit2sMemory limit512 MB

Summary

Sum the K-minsum over all N! permutations, where K-minsum adds the minimum of every contiguous block of length at least K+1.

Level: Hard8 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

A permutation of length $N$ is a sequence built from the $N$ integers $1$ through $N$ , each used exactly once. No value repeats, so there are $N!$ permutations of length $N$ .

Write the elements of a permutation $A$ in order as $A_1, A_2, \dots, A_N$ . The K-minsum of $A$ is

$\text{K-minsum}(A) = \sum_{i=1}^{N} \sum_{j=i+K}^{N} \min(A_i, A_{i+1}, \dots, A_j)$

where $\min$ returns the smallest of the listed numbers. It adds up the minimum of every contiguous block whose length is at least $K+1$ . When $i+K$ is greater than $N$ the inner sum is empty and contributes $0$ .

You are given $N$ and $K$ . Compute the K-minsum of each of the $N!$ permutations of length $N$ and add the results together.

Input

The first line contains the permutation length $N$ and an integer $K$ , separated by a space. ( $1 \le N \le 10^6$ , $0 \le K \le N$ )

Output

Print on one line the sum of the K-minsum over all $N!$ permutations of length $N$ , modulo 1,000,000,007.

Examples6

Example 1
Input
```
1 1
```
Expected output
```
0
```
Example 2
Input
```
2 0
```
Expected output
```
8
```
Example 3
Input
```
3 1
```
Expected output
```
22
```
Example 4
Input
```
5 1
```
Expected output
```
1908
```
Example 5
Input
```
8 2
```
Expected output
```
1435680
```
Example 6
Input
```
13 3
```
Expected output
```
880193815
```