#include<fstream.h>
int s[5010],n,k,p,i,sol=0,x,r,perm[1000],q=0;
int main()
{
ifstream f("sandokan.in");
ofstream g("sandokan.out");

f>>n>>k;

for(i=1;i<=n;i++)
 f>>x;

r=n%(k-1);

 if(!r) p=k-2;

  else p=r-1;

if(!p) g<<"1";

  else

 {

    k=1; s[k]=0;

      while(k>0)

	if(s[k]<n)

	    { s[k]++;

	      if(k==p) sol++;

	       else {k++; s[k]=s[k-1];}
	    }

	  else {k--; if (k==2) { perm[++q]=sol; sol=0;}
		      else if(k==1) break;
	       }
i=1;sol=0;
while(i<=q)

 { for(k=i;k<=q;k++)
    sol+=perm[k];
   i++;
 }


  r=sol%2000003;
  g<<r;
 }

f.close();
g.close();
return 0;
}