思路与算法

固定牡牛数为 $b$。若 $b=0$，只有全牝牛一种。若 $b>0$，在相邻牡牛之间先安排必需的 $K$ 只牝牛，消耗 $K(b-1)$ 个位置。压缩这些固定间隔后，剩余长度 $L=N-K(b-1)$，只需从中选 $b$ 个位置放牡牛，方案数为 $\binom Lb$。压缩与恢复间隔一一对应，未被选的位置放牝牛。

因此答案为

$$1+\sum_{b\ge1,\ N-K(b-1)\ge b}\binom{N-K(b-1)}b\pmod {5000011}.$$

模数是素数，且阶乘上界 $N\le10^5<5000011$，可预处理阶乘、逆阶乘，常数时间求每个组合数。按 $b$ 递增累加，首次 $L<b$ 时终止。间隔压缩值用64位临时变量。

正确性说明

任一合法队列在相邻两牡牛间至少有 $K$ 只牝牛，删除每个间隔最先的这 $K$ 只后，得到长为 $L$ 的普通二元队列及其 $b$ 个牡牛位置。反之，对任意选出的 $b$ 个位置，在每对相邻牡牛之间补回 $K$ 只牝牛，得到且仅得到一个合法原队列。因此固定 $b$ 的队列数为 $\binom Lb$。不同牡牛数的集合互不相交，连同无牡牛方案求和完整覆盖所有队列。

当 $L<b$ 时无法容纳 $b$ 牡牛；以后 $L-b=N+K-(K+1)b$ 继续减小，故终止安全。阶乘均非零模素数，逆阶乘公式合法，逐项取模保持总数余数，输出正确。

复杂度

预处理阶乘和逆阶乘 $O(N)$，一次模逆快速幂 $O(\log P)$，$P=5000011$。枚举 $B=\lfloor(N+K)/(K+1)\rfloor$ 种正牡牛数，时间 $O(B)$。含初始化总时间 $O(N+B+\log P)$，额外空间 $O(N)$。即使 $K$ 很大，阶乘初始化的 $O(N)$ 仍需计入。

易错点

1. 两端不需要牝牛间隔，固定消耗是 $K(b-1)$，不是 $Kb$。
2. 无牡牛方案须额外加1。$K=0$ 时结果为 $2^N$，$K=N-1$ 时最多一只牡牛。
3. 公母牛各自相同，只选位置，不再乘 $b!$。
4. 只在 $0\le b\le L\le N$ 时访问阶乘数组；模数素且预处理上界小于模数是逆阶乘成立条件。
5. 覆盖 $N=1$、最大 $N$、$K=0,1,N-1$；独立答案使用末位符号DP，并以所有 $N\le12$ 二元串枚举核对。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 5000011;
ll power(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1)
            r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> fact(n + 1), inv(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i % MOD;
    inv[n] = power(fact[n], MOD - 2);
    for (int i = n; i; i--)
        inv[i - 1] = inv[i] * i % MOD;
    ll answer = 1;
    for (int bulls = 1; bulls <= n; bulls++) {
        ll spaces = n - 1LL * k * (bulls - 1);
        if (spaces < bulls)
            break;
        ll ways = fact[spaces] * inv[bulls] % MOD * inv[spaces - bulls] % MOD;
        answer = (answer + ways) % MOD;
    }
    cout << answer << '\n';
}