Count Permutations with Bounded Adjacent Difference

Given an integer N and an integer K, consider all permutations of the set \(\{1, 2, \dots, N\}\). A permutation is considered valid if the absolute difference between every two consecutive elements does not exceed \(K\), that is, for a permutation \(a_1, a_2, \dots, a_N\), it holds that \(|a_i - a_{i+1}| \le K\) for \(1 \le i < N\). Your task is to count the number of valid permutations among the total \(N!\) arrangements. Since the answer can be very large, output it modulo \(10^9+7\).

Note: If \(K\) is large enough (i.e. \(K \geq N-1\)), then all permutations are valid.

inputFormat

The input consists of a single line containing two space-separated integers N and K.

\(1 \leq N \leq 16\) (or a similar small constraint that makes the \(O(N \cdot 2^N)\) solution feasible) and \(0 \leq K \leq N\).

outputFormat

Output a single integer: the number of valid permutations modulo \(10^9+7\).

sample

3 1

2