#include <bits/stdc++.h>
#define MOD 2000003
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
long long pwr(long long a, long long p)
{
    if(p==0)
        return 1;
    if(p%2)
        return (a*pwr(a*a%MOD, p/2)%MOD);
    return pwr(a*a%MOD, p/2);
}
long long comb(long long n, long long k)
{
    long long a=1, b=1;
    for(long long i=k+1;i<=n;++i)
        a=a*i%MOD;
    for(long long i=2;i<=n-k;++i)
        b=b*i%MOD;

    b=pwr(b, MOD-2);
    return (a*b)%MOD;
}
long long n, x, k, p;
int main()
{
    fin>>n>>k;
    for(int i=1;i<=n;++i)
        fin>>x;

    p=(n-1)%(k-1)+1;
    fout<<comb(n-1, p-1);

    return 0;
}