Let's call a permutation of n numbers 1 ... n a k - permutation if any two adjacent elements in it differ by no more than k.

Find the number of k-permutations from the numbers 1 ... n.

Input

Two integers n, k (1 ≤ k ≤ n ≤ 9).

Output

Print the number of k-permutations from the numbers 1 ... n.