Description

Original source: USACO 2009 Feb. Silver

牡 mǔ, the male of livestock. 牝 pìn, the female of livestock. ——《Shuowen Jiezi》

John wants to bring $N$ cows to participate in a show at the gathering. These cows can be either male or female. The cows are to stand in a single row, but male cows are aggressive. To prevent any trouble caused by male cows, John decides that there must be at least $K$ female cows between any two male cows.

Please calculate the total number of possible arrangements. All male cows are considered identical, and all female cows are also identical. The answer should be modulo $5000011$.

Input Format

One line containing two integers $N$ and $K$.

Output Format

An integer representing the number of possible arrangements.

Sample 1

The 6 possible arrangements are: FFFF, MFFF, FMFF, FFMF, FFFM, MFFM. (Female Female Female Female, Male Female Female Female, Female Male Female Female, Female Female Male Female, Female Female Female Male, Male Female Female Male)

4 2

6

Data Range and Hint

For all data, $1\le N\le 10^5,0\le K\lt N$.