#include <iostream>
#include <fstream>
#define MOD 2000003
using namespace std;
int n,k,p,c[5002],ant[5002];

ifstream fin("sandokan.in");
ofstream fout("sandokan.out");

int main()
{
    fin >> n >> k;
    p = ((n-1)%(k-1))+1;
    ant[0] = ant[1] = c[0] = 1;
    /// triunghi pascal cu 2 vectori
    for(int i = 2; i <= n-1; i++){
        /// determinam c
        for(int j = 1; j <= i; j++){
            c[j] = (ant[j]+ant[j-1])%MOD;
        }
        /// schimabm ant
        for(int j = 1; j <= i; j++){
            ant[j] = c[j];
        }
    }
    fout << c[p-1] << "\n";
    return 0;
}