#include <fstream>

using namespace std;
int n, k, crt[5010];

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