#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>

// https://infoarena.ro/problema/sandokan

#include <stdio.h>

#define MAX_LEN 20000
#define MAX_NUM 2000003


int main() {
    std::ifstream fin("sandokan.in");
    std::ofstream fout("sandokan.out");
    std::vector<int> a;
    int n, k;

    fin >> n >> k;
    a.resize(MAX_LEN);

    a[0] = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = i; j >= 1; --j) {
            a[j] = (a[j - 1] + a[j]) % MAX_NUM;
        }
    }

    fout << a[(n - 1) % (k - 1)];

    fin.close();
    fout.close();

    return 0;
}