#include <fstream>

using namespace std;
ifstream f("sandokan.in");
ofstream g("sandokan.out");
long long q=2000003;
int main()
{   long long n,k,i,v[5001],nr,a=1,b=1,aux,r,c,x,x0=1,x1=0,p=1,rez=0;
    f>>n>>k;
    for (i=1;i<=n;i++)
        f>>v[i];
    nr=n;
    while (nr>=k)
    {
        nr=nr-(k-1);
    }
    n--;nr--;
    for (i=2;i<=n;i++)
    {
        if (i<=nr) b=(b*(i%q))%q;
        if (i>n-nr) a=(a*(i%q))%q;
    }
    aux=q;
    while (aux!=0)
    {
        r=b%aux;
        c=b/aux;
        b=aux;
        aux=r;
        x=x0-c*x1;
        x0=x1;
        x1=x;
    }
    if (x0<0) x0+=q;
    while (a>0)
    {
        c=a%10;a/=10;
        rez=(rez+((((x0*c)%q)*(p%q))%q))%q;
        p*=10;
    }
    g<<rez;
    return 0;
}