#include<fstream.h>
int s[5010],n,k,p,i,sol=0,x,r;
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--;



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

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