//sandokan -> C(n-1, n%k);
#include <fstream>
#define DIM 2000003
using namespace std;

ifstream fin ("sandokan.in" );
ofstream fout("sandokan.out");

long long n, m, i, j, k, x, val4;
long long val1, val2, maxim, val3;
long long v[5010];

void SetUp(){
    fin >> n >> k;
    val1 = val2 = 1;
    v[0] = 1;
    return;
}

void Combinations(){
    //C(n, k);
    for(i = 1; i < n; i ++)
        for(j = i-1; j >= 1; j --){
            v[j] += v[j-1];
            v[j] %= DIM;
        }
    fout << v[n%(k-1)];
    return;
}

int main(){
    SetUp();
    Combinations();
    return 0;
}