#include <fstream>

using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int n,i,j,k,p,mod=2000003,x;
long long putere(int a,int n)
{
    long long rez=1;
    while (n!=0)
    {
        if (n%2==1) rez=(1LL*rez*a)%mod;
        a=(1LL*a*a)%mod;
        n=n/2;
    }
    return rez;
}
long long factorial(int n)
{
    int i;
    long long fact=1;
    for (i=2;i<=n;i++)
    {
        fact=(fact*i*1LL)%mod;
    }
    return fact;
}
long long invers(int a)
{
    return putere(a,mod-2);
}
int combinari(int n,int k)
{
    int nf=factorial(n);
    int kf=factorial(k);
    int nkf=factorial(n-k);
    int sol=(1LL*nf*invers(kf))%mod;
    sol=(1LL*sol*invers(nkf))%mod;
    return sol;
}
int main()
{
    fin >>n>>k;
    for (i=1;i<=n;i++)
    {
        fin >>x;
    }
    p=(n-1)%(k-1);
    fout <<combinari(n-1,p);
    return 0;
}