#include<stdio.h>
long a[5005],n,k,i,j,p;
int main()
{
 freopen("sandokan.in","r",stdin);
 freopen("sandokan.out","w",stdout);
 scanf("%ld%ld",&n,&p);
 k=n;
 while(k>=p)k-=(p-1);
 a[1]=1;
 a[0]=1;
 for(i=2;i<n;++i)
    for(j=i;j;--j)
       a[j]=(a[j]+a[j-1])%2000003;
 printf("%ld\n",a[k-1]);
 return 0;
}