#include <fstream>
#define MOD 2000003

using namespace std;

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

int n,k,i,j,p,a[2][5005],x,t;

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