/*
* IDEEA DE REZOLVARE:
*
* ELEMENTELE DIN SIR SUNT UNICE!!!
*
* dupa toate eliminarile de elemente va ramane sigur maximul din sir,
* alaturi de alte x elemente,
* deci x = numarul de numere care raman dupa alicarea operatiilor in sir(neconsiderand maximul),
*   x = n - 1; // x este n - 1 deoarece nu  mai consideram maximul din sir
*    while(x >= k - 1) // atata timp cat putem elimina elemente scadem (k -1). scadem (k - 1) deoarece maximul din subsir trebuie sa ramana 
*        x = x - (k - 1); // scadem (k - 1) elemente
* 
* Raspunsul e dat de Combinari(n - 1, x) -> combinari de n - 1 luate cate x
* De ce e raspunsul asa?
* Maximul e mereu in raspuns iar noi mai trebuie sa vedem in cate moduri putem pune n - 1 numere in x pozitii.
* combinam n - 1 elemente deoarece nu mai luam in calcul maximul, acesta avand deja o pozitie in raspuns.
*
* Cum calculam combinarile?
* FOLOSIM triunghiul lui pascal
* triughiul lui pascal poti sa il faci si pe doua dimensiuni
* Gasesti mai multe detalii aici: https://www.pbinfo.ro/articole/10864/triunghiul-lui-pascal
*/

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

ifstream f("sandokan.in");
ofstream g("sandokan.out");
 
const int NMAX = 5'005;
const int MOD = 2'000'003;
 
int n, k, x, pascal[2][NMAX];
 
int main(){
    
    f >> n >> k;
    
     // aflu cate numere o sa ramana dupa aplicarea operatiilor
    x = n - 1;
    while(x >= k - 1)
        x = x - (k - 1);
    
    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;
    }
    
    g << pascal[(n - 1) % 2][x];
    
    return 0;
}