#include <fstream>

std::ifstream f("sandokan.in");
std::ofstream g("sandokan.out");

const int NMAX = 5005;
const int MOD = 2'000'003;

int n,k,x,pascal[2][NMAX];

int main(){
    
    f >> n >> k;
    
    pascal[0][0] = 1;
    
    for(int i = 1;i < n;++i){
        
        for(int j = 0;j <= i;++j)
            if(j == 0 || j == i)
                pascal[i % 2][j] = 1;
            else
                pascal[i % 2][j] = (pascal[1 - i % 2][j] + pascal[1 - i % 2][j - 1]) % MOD;
    }
    
    x = (n - 1) % (k - 1);
    g << pascal[(n - 1) % 2][x];
    
    return 0;
}