#include <bits/stdc++.h>
using namespace std;
#define MOD 2000003
#define TH 100001
ifstream f("sandokan.in");
ofstream g("sandokan.out");
int n,k,a[5001],nrprime,prime[40001],imax;
bool c[100001];
int F[40001];
int rez;
void genciur()
{   c[0]=c[1]=1;
    for(int i=2;i*i<=TH;i++)
        if(c[i]==0)
            for(int j=2;i*j<=TH;j++) c[i*j]=1;
    for(int i=1;i<=TH;i++) if(!c[i]) prime[++nrprime]=1;
}
int main()
{   f>>n>>k;
    for(int i=1;i<=n;i++) f>>a[i];
    int c1=n-1;
    int c2=(n-1)%(k-1);
    genciur();
    for(int x=c1;x>=c1-c2+1;x--)
    {   int y=x;
        int i=1;
        while(y>1)
        {   while(y%prime[i]==0)
            {   y/=prime[i];
                F[prime[i]]++;
                if(i>imax) imax=i;
            }
            i++;
        }
    }
    for(int x=1;x<=c2;x++)
    {   int y=x;
        int i=1;
        while(y>1)
        {   while(y%prime[i]==0)
            {   y/=prime[i];
                F[prime[i]]--;
            }
            i--;
        }
    }
    rez=1;
    for(int i=1;i<=imax;i++)
        while(F[prime[i]]--) rez=(rez*prime[i])%MOD;
    g<<rez<<'\n';
    return 0;
}