#include <iostream>
#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;
    
     // aflu cate numere o sa ramana dupa aplicarea operatiilor
    x = n - 1;
    while(x >= k - 1)
        x = x - (k - 1);
    
    // elementele din v sunt unice
    // Calulez C(n - 1,x - 1)
    // n - nr de elemente al sirului
    // x - nr de elemente ramase dupa aplicarea opertiilor
    // n - 1 deoarece nu maximul mereu o sa se afle in secventa
    // x - 1 deoarece nu ma intereseaza maximul
    
    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;
    }
    
    g << pascal[(n - 1) % 2][x];
    
    return 0;
}