#include <fstream>
using namespace std;
ifstream cin("sandokan.in");
ofstream cout("sandokan.out");
int  n,k,i,j,t,b[3][5000],x;
int main()
{
    cin>>n>>k;
    b[1][0]=1;
    for (i=1;i<n;i++)
    {
        for (j=1;j<=k;j++)
            b[2][j]=b[1][j-1]+b[1][j];
        for (j=1;j<=k;j++)
            b[1][j]=b[2][j]%2000003;
    }
    x=n;
    while(x>=k)
	    x=x%k+x/k;
    cout<<b[1][x-1]<<" ";
    return 0;
}