好的，我把这道题整理成标准的题面格式，补充样例解释、数据范围、时空限制：

题目描述

原题来自：USACO 2009 Feb. Silver

牡（mǔ），畜父也。牝（pìn），畜母也。——《说文解字》

约翰要带 $N$ 只牛去参加集会里的展示活动，这些牛可以是牡牛（公牛），也可以是牝牛（母牛）。牛们要站成一排，但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决定任意两只牡牛之间至少要有 $K$ 只牝牛。

请计算一共有多少种排队的方法，所有牡牛可以看成是相同的，所有牝牛也一样，答案对 $5000011$ 取模。

输入格式

一行，输入两个整数 $N$ 和 $K$。

输出格式

一个整数，表示排队的方法数。

样例

样例输入 1

4 2

样例输出 1

6

样例解释 1

$N=4, K=2$，表示任意两只牡牛之间至少有 $2$ 只牝牛。
所有可能的排法如下（用0表示牝牛，1表示牡牛）：

1. 0000
2. 1000
3. 0100
4. 0010
5. 0001
6. 1001

总共 $6$ 种。

数据范围

• 对于 $30\%$ 的数据，$1 \le N \le 10$；
• 对于 $60\%$ 的数据，$1 \le N \le 1000$；
• 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le K < N$。

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

提示
假设有 $m$ 只牡牛，那么它们之间至少有 $K$ 只牝牛，可以把每只牡牛和它后面紧跟着的 $K$ 只牝牛（最后一只牡牛后面可以没有牝牛）看作一组，使用组合数学或递推计算。也可递推：设 $dp[i]$ 表示前 $i$ 头牛的合法方案数，转移时考虑最后一头是牝牛还是牡牛。