#include <fstream>
#define DIM 2000003
using namespace std;

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

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

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

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

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