#include<fstream>
#define MOD 2000003
using namespace std;
ifstream fi("sandokan.in");
ofstream fo("sandokan.out");
int n,k,p,i,j,C[3][5001];
int main()
{
    fi>>n>>k;
    p=(n-1)%(k-1);
    //C(n-1,p)
    C[0][0]=1;
    for(i=1; i<n; i++)
    {
        C[i%2][0]=1;
        for(j=1; j<=i; j++)
        {
            C[i%2][j]=(C[1-i%2][j-1]+C[1-i%2][j])%MOD;
        }
    }
    fo<<C[(n-1)%2][p]<<"\n";
    fi.close();
    fo.close();
    return 0;
}