#include <fstream>

using namespace std;
ifstream f("sandokan.in");
ofstream g("sandokan.out");
int n,k,a[5005];
const int mod=2e6+3;
int main()
{
    f>>n>>k;
    a[1]=1;
    n--;
    k=n%(k-1);
    for(int i=2;i<=n+1;i++)
        for(int j=i;j;j--)
            a[j]=(a[j-1]+a[j])%mod;
    g<<a[k+1];
    return 0;
}