Description

We know there are $N!$ permutations of the $N$ numbers $1,2,...,N$. Your task is to count how many of these permutations have the property that the difference between any two adjacent numbers does not exceed $K$.

Since the result may be large, output the answer modulo $10^9+7$.

Input Format

The input contains a single line with two space-separated integers: $N, K$.

Output Format

Output the number of valid permutations modulo $10^9+7$.

4 2

12

Hint

On 30% of the testdata, $N \le 12$.

On 100% of the testdata, $N \le 50$, $K \le 4$.

Time limit per test point: 10 seconds.

Translated by ChatGPT 5