P3867 [TJOI2009] Permutation Counting

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$.

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

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

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