#include <cstdio>
#include <algorithm>
#define MOD 2000003
using namespace std;
long long a[5001];
double p;
double rest(double x, int y)
{
    int nr=0;
    while (x>=y)
    {
        x=x-y;
        nr++;
    }
    return x-y*nr;
}
int aprox(double p)
{
    if ((p-(int)(p))<0.00001) return (int)(p);
    if ((p-(int)(p))>0.99999) return (int)(p)+1;
}
int n,k,nrmax,nridentice,i,x,y;
long long Max;
int main()
{
    freopen("sandokan.in","r",stdin);
    freopen("sandokan.out","w",stdout);
    scanf("%d %d\n",&n,&k);
    Max=-1;
    nrmax=nridentice=0;
    for (i=1; i<=n; i++) scanf("%d",&a[i]);
    for (i=1; i<=n; i++)
    {
        if (a[i]>Max)
        {
            Max=a[i];
            nrmax=1;
        }
        else if (a[i]==Max) nrmax++;
    }
    sort(a+1,a+n+1);
    for (i=2; i<=n; i++) if (a[i]==a[i-1] && a[i]!=Max) nridentice++;
    y=n-(k-1)*((n-k)/(k-1)+1);
    y=y-nrmax;
    x=n-nrmax-nridentice;
    if (x<0 || y<0) printf("0\n");
    else
    {
        if (x<y) printf("1\n");
        else
        {
            p=1;
            for (i=1; i<=x-y; i++)
            {
                p=p*(1.0*(y+i))/(1.0*i);
                p=rest(p,MOD);
            }
            printf("%d\n",aprox(p));
        }
    }
    return 0;
}