#include <iostream>
#include <cstdio>
#define MOD 2000003

using namespace std;

int put(int nr, int p)
{
    int rez = 1;
    for (int i = 0; p >> i; i++) {
        if ((p>>i) & 1)
            rez = (1LL*rez*nr) % MOD;
        nr = (1LL*nr*nr) % MOD;
    }
    return rez;
}

int inv(int nr)
{
    return put(nr, MOD-2);
}

int fact(int n)
{
    if (n <= 1)
        return 1;
    return 1LL*n*fact(n-1) % MOD;
}

int comb(int n, int k)
{
    return (1LL*fact(n)*inv(fact(n-k))*inv(fact(k)))%MOD;
}

int main()
{
    freopen("sandokan.in", "r", stdin);
    freopen("sandokan.out", "w", stdout);

    int n, k, x;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &x);
    int sol = comb(n-1, (n-1)%(k-1));
    printf("%d", sol);

    return 0;
}