#include <fstream>

using namespace std;
ifstream cin("sandokan.in");
ofstream cout("sandokan.out");
const int MOD=2000003;
unsigned long long fact[5005];
unsigned long long p2(unsigned long long a, unsigned long long b)
{
    unsigned long long put=1;
    while(b)
    {
        if(b%2)
            put=put*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return put;
}
signed main()
{
    int n,m,nr;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>nr;
    fact[0]=fact[1]=1;
    for(int i=2;i<=5000;i++)
        fact[i]=(fact[i-1]*i)%MOD;
    n--;
    m=n%(m-1);
    cout<<1LL*(fact[n]*p2(fact[n-m],MOD-2)%MOD)*p2(fact[m],MOD-2)%MOD;
    return 0;
}