#include <bits/stdc++.h>
#define MOD  2000003

using namespace std;

int n,k;

int dp[2][5003];

int main()
{
    freopen("sandokan.in","r",stdin);
    freopen("sandokan.out","w",stdout);
    scanf("%d %d",&n,&k);
    int aux = n;
    while(aux >= k) {
        aux -= (k-1);
    }
    n--;aux--;
    int line = 1;
    dp[line ^ 1][1] = 1;
    dp[line ^ 1][0] = 1;
    for(int i = 1; i < n; i++) {
        dp[line][0] = 1;
        for(int j = 1; j <= k; j++) {
            dp[line][j] = (dp[line ^ 1][j - 1] + dp[line ^ 1][j]) % MOD;
        }
        line = line ^ 1;
    }
    printf("%d",dp[line][aux]);

    return 0;
}