#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("sandokan.in");
ofstream fout("sandokan.out");

const int mod = 2'000'003;
int n, k, r, fact[5005];
long long ans, x, y;

long long lgput(int a, int p)
{
    if(p == 0)
        return 1;
    if(p % 2 == 0)
    {
        long long k = lgput(a, p / 2);
        return k * k % mod;
    }
    else
        return a * lgput(a, p - 1) % mod;
}

int main()
{
    fin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        int nr;
        fin >> nr;
    }
    r = (n - 1) % (k - 1) + 1;
    n--, r--;
    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = (fact[i - 1] * i) % mod;
    ans = fact[n];
    x = lgput(fact[r], mod - 2);
    ans = (ans * x) % mod;
    x = lgput(fact[n - r], mod - 2);
    ans = (ans * x) % mod;
    fout << ans;
    return 0;
}