Counting Permutations with Non‐Trivial Contiguous Segments

Let \(p = (p_1, p_2, \dots, p_n)\) be a permutation of \(\{1,2,\dots,n\}\). For any interval \([l, r]\) (with \(1 \le l < r \le n\)), we call \([l, r]\) a contiguous segment if \[ \max_{l\le i\le r} p_i - \min_{l\le i\le r} p_i = r - l. \] A contiguous segment \([l, r]\) is called non‐trivial if additionally it satisfies \[ 2 \le r-l+1

We say that a permutation (p) embodies the state of mind of the youth if there exists at least one non‐trivial contiguous segment whose length is greater than (k) (i.e. (r - l + 1 > k)).

Given two integers (n) and (k), count the number of (n)th order permutations that satisfy this property. Since the answer can be large, output it modulo (10^9+7).

Note: A contiguous segment \([l,r]\) of a permutation \(p\) is said to be contiguous if the set \(\{p_l, p_{l+1},\dots, p_r\}\) consists of consecutive integers (in any order).

inputFormat

The input consists of a single line containing two integers \(n\) and \(k\) (separated by a space).

outputFormat

Output a single integer — the number of \(n\)th order permutations that have at least one non‐trivial contiguous segment of length greater than \(k\), taken modulo \(10^9+7\).

sample

3 1

6