#include <bits/stdc++.h>
#define N 5005
#define MOD 2000003

using namespace std;

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

int cmb[3][N] ;

int main()
{
    int i , j , n , k , x , p , w ;
    fin >> n >> k ;
    x = n%(k-1) ;
    if ( x == 0 )
        x = k-1 ;
    cmb[0][0] = 0 ;
    p = 0 ;
    w = 1 ;
    for ( i = 0 ; i < n ; i++ )
    {
        p = 1-p ;
        w = 1-w ;
        for ( j = 0 ; j <= i ; j++ )
        {
            if ( j == 0 )
                cmb[p][j] = 1 ;
            else
                cmb[p][j] = (cmb[w][j]+cmb[w][j-1]) % MOD ;
        }
    }
    fout << cmb[p][x-1] ;
}