为了简化，将两种牛分成01。

• 状态表示：$f[i]$表示有i个数，最后一位是1的方案总数。

• 划分方式：倒数第二个1的位置。

• 状态计算：$f[i] = f[i-k-1]+f[i-k-2]+…+f[0]$。

• 状态划分：求的是所有方案，将所有方案以最后一个1所在位置划分为：第0位(没有1)、第一位、第二位、… ，即$f[0]+f[1]+f[2]+…+f[n]$，也就是f[]数组的前缀和，同时发现f[i]也就等于s[i-k-1]

#include <iostream>

using namespace std;

const int N = 100010 , mod = 5000011 ;

int f[N] , s[N];

int main()
{
    int n , k;
    cin >> n >> k;

    f[0] = s[0] = 1;//当i-k-1<0时，因为在i是1前面全是0的方案是可行的，所以为了加上这个方案，需要把f[0]设置为1
    for(int i = 1 ; i <= n ; i++)
    {
        f[i] = s[max(i - k - 1 , 0)];
        s[i] = (s[i - 1] + f[i]) % mod;
    }

    cout << s[n] << endl;
    return 0;
}