题目描述

学校科技节准备布置一条长廊。长廊中有一排 $N$ 个位置，每个位置必须放置一盏彩灯或一个气球。

为了使气球之间留有足够空间，任意两个气球之间必须至少放置 $K$ 盏彩灯。请计算共有多少种符合要求的布置方案。

所有彩灯都相同，所有气球也相同。只要两个方案中至少有一个位置放置的物品不同，就认为它们是不同的方案。

输入格式

第一行包含两个整数 $N$ 和 $K$，分别表示长廊中的位置数量，以及任意两个气球之间至少需要放置的彩灯数量。

输出格式

输出一个整数，表示符合要求的布置方案数量对 $5000011$ 取模后的结果。

4 2

6

99 17

414595

10000 398

1474315

样例解释

共有 $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$。