Bulls and Cows

Interview

Time limit1sMemory limit128 MB

Summary

Count binary sequences of length N where every pair of bulls has at least K cows between them, modulo 5000011.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Prefix sum
Solved: No attempts yet

Problem

Farmer John wants to arrange $N$ animals ( $1 \le N \le 100{,}000$ ) — bulls and cows — in a single row to present at the annual fair.

FJ has noticed that the bulls have become quite pugnacious lately: if two bulls stand too close together in the line, they will argue and start to fight, ruining the presentation. Being resourceful, FJ has calculated that any two bulls must have at least $K$ cows ( $0 \le K < N$ ) between them in order to avoid a fight.

Help FJ by counting the number of distinct sequences of $N$ bulls and cows that avoid any fighting. All bulls are identical and all cows are identical, so two sequences differ only if some position holds a different kind of animal.

Input

Line 1: Two space-separated integers, $N$ and $K$ .

Output

Line 1: A single integer — the number of sequences FJ could create. Because this number can be very large, output it modulo $5{,}000{,}011$ .

Hint

For $N = 4$ and $K = 2$ , the six sequences FJ could create are shown below ('C' is a cow and 'B' is a bull):

CCCC
BCCC
CBCC
CCBC
CCCB
BCCB

Examples3

Example 1
Input
```
4 2
```
Expected output
```
6
```
Example 2
Input
```
1 0
```
Expected output
```
2
```
Example 3
Input
```
2 1
```
Expected output
```
3
```