#include <iostream>
#include <fstream>
#define int unsigned long long
#define mod 2000003

int fact[5001], v[5001];

int lgpow(int a, int b)
{
    int rez = 1;
    while(b > 0)
    {
        if(b & 1)
        {
            rez = rez * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return rez;
}

int combinari(int n, int k)
{
    return fact[n] * lgpow(fact[k] * fact[n - k] % mod, mod - 2) % mod;
}

using namespace std;

signed main()
{
    ifstream cin("sandokan.in");
    ofstream cout("sandokan.out");
    int n, k, i;
    cin >> n >> k;
    for(i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    fact[0] = 1;
    for(i = 1; i <= n; i++)
    {
        fact[i] = i * fact[i - 1] % mod;
    }
    cout << combinari(n - 1, (n - 1) % (k - 1));
    return 0;
}