#include <fstream>
#define dim 5010
#define mod 2000003
using namespace std;
int c[dim];
int i,j,k,n,x;

int main() {
    ifstream fin("sandokan.in");
    ofstream fout("sandokan.out");
    fin>>n>>k;
    x=n;
    while (x>=k) {
        x-=k-1;
    }
    x--;
    n--;
    c[0]=1;
    for (i=1;i<=n;i++) {
        for (j=i;j>=1;j--) {
            c[j]=(c[j]+c[j-1])%mod;
        }
    }
 //   for (i=0;i<=n;i++) fout<<c[i]<<" ";
 //   fout<<"\n";
    ///rezultatul este Combinari de n-1 luate cate x
    ///deoarece mereu o sa fie inclus maximul din sir
    fout<<(c[x])%mod;
    return 0;
}