题目描述

一年一度的灯会即将在古镇拉开帷幕，灯艺师小 A 计划在一长条横幅上布置 $N$ 个灯饰材料。这些灯饰材料由两种类型组成：闪烁的彩灯和膨胀的气球。气球体积较大，若相邻放置过密，便会相互挤压碰撞，影响整体美观，也影响安全。

小 A 深谙布置的技巧，他规定任意两个气球之间须至少间隔 $K$ 个彩灯，才能确保美观和安全。他希望借助你的智慧，计算出所有可能的布置方案数量。

彩灯之间没有区别、气球之间也没有区别。如果有两个布置方案，在同一个位置上使用了不同的灯饰材料，则算作不同的布置方案。

输入格式

一行，两个整数 $N$ 和 $K$，用一个空格隔开。

输出格式

一行一个整数，表示可行的布置方案总数对 $5000011$ 取模后的结果。

样例

4 2

6

99 17

414595

10000 398

1474315

样例 1 解释

共有 $6$ 种不同的布置方案（L 表示彩灯，G 表示气球）：LLLL、GLLL、LGLL、LLGL、LLLG、GLLG。

数据范围

• $1 \le N \le 10^5$，$0 \le K < N$。
• 测试点 $1$：$N \le 10$，$K=0$。
• 测试点 $2$：$N \le 10$，$K=3$。
• 测试点 $3$：$N \le 20$，$K=2$。
• 测试点 $4$：$N \le 40$，$K=7$。
• 测试点 $5$：$N \le 230$，$K=4$。
• 测试点 $6 \sim 10$：$N \le 10^5$，$K < N$。