Restricted Permutations

Time limit2sMemory limit128 MB

Summary

Count permutations of 1..N where every element differs from its index by at most K, using a bitmask DP over a sliding window.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Combinatorics, Math
Solved: No attempts yet

Problem

A permutation of length N is an arrangement that uses each integer from 1 through N exactly once. There are N! = N × (N - 1) × ... × 2 × 1 such permutations.

For a permutation P, let P[i] be its i-th element. Count the permutations P such that |P[i] - i| <= K for every 1 <= i <= N.

Input

The first line contains two positive integers N and K separated by a space. N is at most 100, and K is at most 6.

Output

Print the number of permutations that satisfy the condition.

Examples4

Example 1
Input
```
3 1
```
Expected output
```
3
```
Example 2
Input
```
3 2
```
Expected output
```
6
```
Example 3
Input
```
10 3
```
Expected output
```
19708
```
Example 4
Input
```
100 1
```
Expected output
```
573147844013817084101
```