#include <iostream>
#include <fstream>
using namespace std;
ifstream in("sandokan.in");
ofstream out("sandokan.out");

const int MOD = 2000003;
int fact[5001];

void preCalcFact(int n)
{
    fact[0] = 1;
    fact[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
}


long long power(long long base, int exp)
{
    long long p = 1;
    while(exp > 0)
    {
        if(exp % 2 == 1)
        {
            p = (p * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return p;
}


long long C(int n, int k)
{
    int numarator = fact[n];
    int numitor = (fact[n - k] * fact[k]) % MOD;
    return numarator * power(numitor, MOD - 2) % MOD;
}

int main()
{
    int n, k, nr;
    in >> n >> k;
    preCalcFact(n);
    for(int i = 1; i <= n; i++)
    {
        in >> nr;
    }
    out << C(n - 1, (n - 1) % (k - 1)) % MOD;
    return 0;
}