#include <fstream>

using namespace std;
ifstream f("sandokan.in");
ofstream g("sandokan.out");
int q=2000003;
int main()
{   int n,k,i,v[5001],nr,a=1,b=1,aux,r,c,x,x0=1,x1=0;
    f>>n>>k;
    for (i=1;i<=n;i++)
        f>>v[i];
    if (k==n) g<<1;
    else
    {nr=n;
    while (nr>k)
    {
        nr-=k;
    }
    for (i=1;i<=n-1;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;
    g<<(x0*a)%q;
    }
    return 0;
}