#pragma GCC optimize("O3")
#pragma GCC  optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#include<bits/stdc++.h>
#define mod 2000003
#define ll long long
using namespace std;
int n, k, v[5005];
ll sol, fact[5005];
void precalc()
{
    fact[0] = 1;
    for(int i = 2; i <= 5000; ++i)
    {
        fact[i] = (fact[i - 1] * 1ll * i) % mod;
    }
}
ll putere(ll a, ll b)
{
    ll p = 1;
    while(b)
    {
        if(b & 1)
        {
            p = 1ll * (p * a) % mod;
        }
        b >>= 1;
        a = (a * a) % mod;
    }
    return p % mod;
}
ll calculate_combinatorics(ll n, ll k)
{
    if(n < k)
    {
        return 0;
    }
    return 1ll * (fact[n] % mod * putere(fact[n - k], mod - 2) % mod * 1ll * putere(fact[k], mod - 2) % mod) % mod;
}
inline void Open(const string& name)
{
    #ifndef ONLINE_JUDGE
    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
    #endif // ONLINE_JUDGE
}
int32_t main(int argc, char * argv[])
{
    Open("sandokan");
    precalc();
    cin >> n >> k;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i = 1; i <= n; ++i)
    {
        cin >> v[i];
    }
    if(k == n)
    {
        cout << 1;
        return 0;
    }
    ll nr = 0;
    nr = calculate_combinatorics(n - 1, (n - 1) % (k - 1) + 1);
    cout << nr % mod;
    return 0;

}