#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
 
const int NMAX = 5010, MOD = 2000003;
 
int N, K, V[NMAX], Fact[NMAX];
 
int LgPow(int N, int P)
{
    if(!P) return 1;
    if(P % 2) return (1LL * N * LgPow(N, P - 1)) % MOD;
    int X = LgPow(N, P / 2);
    return (1LL * X * X) % MOD;
}
 
int Comb(int N, int K)
{
    if(K <= 0 || K >= N - 1) return 1;
    int A = Fact[N], B = (1LL * Fact[K] * Fact[N - K]) % MOD;
    return (1LL * A * LgPow(B, MOD - 2)) % MOD;
}
 
int main()
{
    freopen("sandokan.in", "r", stdin);
    freopen("sandokan.out", "w", stdout);
 
    scanf("%i %i", &N, &K);
    Fact[0] = 1;
    for(int i = 1; i <= N; ++ i)
    {
        scanf("%i", &V[i]);
        Fact[i] = (1LL * Fact[i - 1] * i) % MOD;
    }
 
    int X = N;
    while(X > K - 1) X -= K - 1;
 
    printf("%i\n", Comb(N - 1, X - 1));
 
    return 0;
}