#include <stdio.h>
#include <math.h>
int i,j,k,n,m,d,x;
int a[5010],elem[5010],imp[5010];
int cmmdc(int a, int b)
{
    int x=a,y=b,r;

    while (x%y!=0)
    {
        r=x%y;
        x=y;
        y=r;
    }
    return y;
}
long long comb(int p, int q)
{
    for (i=1; i<=p; i++)
        elem[i]=i;

    //impart la q!
    for (i=1; i<=q; i++) imp[i]=i;

    for (i=1; i<=p; i++)
        for (j=1; j<=q; j++)
        if (elem[i]>1)
        {
            int x=cmmdc(elem[i],imp[j]);
            elem[i]/=x;
            imp[j]/=x;
        }
        else break;

    //impart la (p-q)!
    for (i=1; i<=p-q; i++) imp[i]=i;

    for (i=1; i<=p; i++)
        for (j=1; j<=p-q; j++)
        if (elem[i]>1)
        {
            int x=cmmdc(elem[i],imp[j]);
            elem[i]/=x;
            imp[j]/=x;
        }
        else break;

    //calculez produsul
    long long sol=1;
    for (i=1; i<=p; i++)
        sol=(sol*elem[i])%2000003;
    return sol;
}
int main()
{
    freopen("sandokan.in","r",stdin);
    freopen("sandokan.out","w",stdout);

    scanf("%d %d",&n,&k);
    for (i=1; i<=n; i++)
        scanf("%d",&a[i]);

    for (i=1; i<=n-1; i++)
        for (j=i+1; j<=n; j++)
            if (a[i]>a[j])
            {
                x=a[i];
                a[i]=a[j];
                a[j]=x;
            }

    m=0;
    for (i=1; i<=n; i++)
        if (a[i]!=a[i-1]) m++;

    d=cmmdc(n,k-1);
    long long sol=comb(m-1,d-1);

    printf("%lld\n",sol);
    
    return 0;
}