#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=q+1; i<=p; i++)
        elem[i-q]=i;

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

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

    //calculez produsul
    long long sol=1;
    for (i=q+1; i<=p; i++)
        sol=(sol*elem[i-q])%2000003;
        */
    
    long long sol=1;
    for (i=q+1; i<=p; i++)
        sol=(sol*i)%2000003;
    for (i=1; i<=p-q; i++)
        sol=(sol/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]);

    d=n%(k-1);
    if (d==0) d=k-1;
    
    long long sol=comb(n-1,d-1);

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