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

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

#ifndef MAX(X, Y)
#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
#endif // !MAX

#include <stdio.h>

#define MAX_LEN 6000
#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(n);
    int maxj = 0;
    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;
            maxj = MAX(j, maxj);
        }
    }

    fout << a[(n - 1) % (k - 1)];
    std::cout << maxj;
    fin.close();
    fout.close();

    return 0;
}