#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;

const string file = "sandokan";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647, M = 2000003;

int n, k, pas[2][5005];

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n >> k;
    pas[0][0] = 1;
    for (int i = 1; i < n; ++i){
        pas[i%2][0] = 1;
        for (int j = 1; j <= i; ++j)
            pas[i%2][j] = (pas[(i-1)%2][j]+pas[(i-1)%2][j-1])%M;
    }
    fout << pas[(n-1)%2][(n-1)%(k-1)] << "\n";
    return 0;
}