#include <fstream>
#include <cstring>
using namespace std;

ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int n,k;

const int modulo = 2000003;

int c[10000];
int a[10000];



int main()
{
    fin>>n>>k;
    c[0]=1;
    a[0]=1;
    a[1]=1;
    for(int i=2;i<=n-1;i++)
    {
        for(int j=1;j<=i;j++)
        {
            c[j]= a[j]+a[j-1];
            if(c[j]>modulo)
                c[j]%=modulo;
        }
        memcpy(a,c,sizeof(c));

    }
    fout<<c[(n-1)%(k-1)];


}