Crossing the stepping stones backward

Time limit2sMemory limit1024 MB

Summary

Count the self-avoiding paths from stone 1 to stone N when each move jumps forward by 1 to K or steps back by 1, modulo 1000000007.

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

Problem

Stones numbered $1$ through $N$ are placed in a row in order. Starting from stone $1$ , you move toward stone $N$ under the following rules.

From stone $i$ , you can move to stone $i+x$ for an integer $x$ with $1\le x\le K$ .
From stone $i$ , you can move to stone $i-1$ .
You cannot move to a position where there is no stone.
Including the start and the end, you cannot step on a stone you have already stepped on.

Find the number of ways to move from stone $1$ to stone $N$ under these rules, modulo $1\,000\,000\,007 (=10^9+7)$ . Two moves are different if the sequences of stone numbers stepped on are different.

Input

The first line contains the number of stones $N$ and the integer $K$ , separated by a space. ( $1\le N\le 2\,000$ ; $1\le K\le 50$ )

Output

On the first line, print the number of ways to move from stone $1$ to stone $N$ under the rules, modulo $1\,000\,000\,007 (=10^9+7)$ .

Examples3

Example 1
Input
```
5 3
```
Expected output
```
12
```
Example 2
Input
```
8 4
```
Expected output
```
191
```
Example 3
Input
```
1923 45
```
Expected output
```
703532137
```