Description

Given a permutation of order $n$ $p_1,\dots,p_n$ and an interval $[l,r]$, if $\max\limits_{l\le i\le r} p_i - \min\limits_{l\le i\le r} p_i = r - l$, then $[l,r]$ is called a consecutive segment.

For a consecutive segment $[l,r]$, if it satisfies $2 \le r - l + 1 < n$, then $[l,r]$ is called a non-trivial consecutive segment.

The boy’s thoughts can be abstracted as a permutation that has at least one non-trivial consecutive segment with length greater than $k$.

The boy will give $n,k$ and ask you how many permutations of order $n$ can be the boy’s thoughts. Output the answer modulo $10^9 + 7$.

Input Format

The first line contains two positive integers $n,k$.

Output Format

One line containing one non-negative integer, representing the answer.

3 2

0

4 2

20

Hint

For $20\%$ of the testdata, $n \le 10$.
For $100\%$ of the testdata, $1 \le k < n \le 400$.

Sample Explanation

For the second sample, there are $4$ permutations that do not satisfy the condition:

1. $[2,1,4,3]$.
2. $[2,4,1,3]$.
3. $[3,4,1,2]$.
4. $[3,1,4,2]$.

The other $4!-4=20$ cases all satisfy the condition and can be the boy’s thoughts.

Translated by ChatGPT 5