当前没有测试数据。

题目描述

一年一度的灯会即将在古镇拉开帷幕，灯艺师小A计划在一长条横幅上布置 N 个灯饰材料。这些灯饰材料由两种类型组成：闪烁的彩灯和膨胀的气球。气球体积较大，若相邻放置过密，便会相互挤压碰撞，影响整体美观，也影响安全。 小A深谙布置的技巧，他规定任意两个气球之间须至少间隔 K 个彩灯，才能确保美观和安全。他希望借助你的智慧，计算出所有可能的布置方案数量。彩灯之间没有区别、气球之间也没有区别，如果有 2 个布置方案，在同一个位置上使用了不同的灯饰材料，则算作不同的布置方案。

输入格式

一行两个整数 N 和 K。

输出格式

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

样例输入 1

4 2

样例输出 1

6

样例输入 2

99 17

样例输出 2

414595

样例输入 3

10000 398

样例输出 3

1474315

样例说明

样例 1 说明： 有 6 种不同的布置效果（L 表示彩灯，G 表示气球）：LLLL、GLLL、LGLL、LLGL、LLLG、GLLG。

数据范围

• 对于 100% 的数据，满足 1 ≤ N ≤ 1e5，0 ≤ K < N。
• 测试点 1：N ≤ 10，K=0。
• 测试点 2：N ≤ 10，K=3。
• 测试点 3：N ≤ 20，K=2。
• 测试点 4：N ≤ 40，K=7。
• 测试点 5：N ≤ 230，K=4。
• 测试点 6~10：N ≤ 1e5，K < N。