#include <iostream>
#include <fstream>
#include <vector>

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

#define MAX_NUM 2000003


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

    fin >> n >> k;
    a.resize(n);
    int maxj = 0;
    a[0] = 1;
    for (i = 1; i < n; ++i) {
        for (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;
}