#include <bits/stdc++.h>
using namespace std;
#define MOD 2000003
ifstream in("sandokan.in");
ofstream out("sandokan.out");
int fact[5001],invfact[5001];
void factoriale(int n)
{
fact[0]=1;
for(int i=1;i<=n;i++){
fact[i]=(1LL*fact[i-1]*i)%MOD;
}
}
int dot_product(int baza, int p)
{
int rez=1;
while(p>0)
{
if(p&1){
rez=(1LL*rez*baza)%MOD;
}
p/=2;
baza=(1LL*baza*baza)%MOD;
}
return rez;
}
void inversmodfactoriale(int n)
{
invfact[n]=dot_product(fact[n], MOD-2);
for(int i=n-1;i>=0;i--){
invfact[i]=(1LL*invfact[i+1]*(i+1))%MOD;
}
}
int main()
{
int n,k,sol=1,r;
in>>n>>k;
for(int i=1;i<=n;i++){int x; in>>x;}
r=(n-1)%(k-1)+1;
factoriale(n);
inversmodfactoriale(n);
sol=fact[n-1];
sol=(1LL*sol*invfact[r-1])%MOD;
sol=(1LL*sol*invfact[n-r])%MOD;
out<<sol;
return 0;
}