#include <cstdio>
#include <vector>
#define mod 2000003

using namespace std;

vector <int> v;
int n,k,p;

void citire()
{
    freopen("sandokan.in","r",stdin);
    scanf("%d%d", &n, &k);
    int w;
    for (int i=0; i<n; i++)
    {
        scanf("%d", &w);
        v.push_back(w);
    }
}

int cmmdc(int a, int b)
{
	int w=a;
	int q=b;
	int r;
	while (q>0)
	{
		r=w%q;
		w=q;
		q=r;
	}
	return w;
}

void sandokan()
{
    //sort(q.begin(),q.end());
    p=n%(k-1);
    int w=1;
    for (int i=2; i<p; i++)
        w*=i;
    long long rez=1;
    int c,q;
    for (int i=n-p+1; i<n; i++)
    {
        q=i;
        c=cmmdc(i,w);
        q/=c;
        w/=c;
        rez*=q;
        rez%=mod;
    }
    rez%=mod;
    freopen("sandokan.out","w",stdout);
    printf("%lld",rez);
}

int main()
{
    citire();
    sandokan();
    return 0;
}