#include <cstdio>

#define N 100004

#define mod 5000011

#define setIO(s) freopen(s".in", "r" , stdin)

using namespace std;

int f[N][2];

int main()

{

    // setIO("input");

    int n , k, i ;

    scanf("%d%d", &n, &k);

    f[1][0] = f[1][1] = 1;

    for(i = 2; i <= n ; ++ i)

    {

        f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;

        if(i > k) f[i][1] = f[i - k][0];

        else f[i][1] = 1;

    }

    printf("%d\n", (f[n][0] + f[n][1]) % mod);

    return 0;

}