#include <fstream>

using namespace std;
ifstream f("sandokan.in");
ofstream g("sandokan.out");
const int mod=2000003;
int n,k,x,a[5002];
int main()
{
    f>>n>>k;
    x=n%(k-1);
    if(x==0)
    {
        x=k-1;
    }
    x--;
    for(int i=1;i<n;i++)
    {
        a[0]=1;
        for(int j=i;j>0;j--)
        {
            a[j]=(a[j]+a[j-1])%mod;
        }
    }
    g<<a[x]<<'\n';
    return 0;
}