#include<fstream>
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>

#define MOD 2000003

using namespace std;

//ifstream f("in.in");
//ofstream g("out.out");

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

int C[5005];

int main()
{
    int n,k,p,x;
    f>>n>>k;
    for(int i=1;i<=n;i++)
    {
        f>>x;
    }

    p=(n-1)%(k-1)+1;

    C[0]=1;
    C[1]=1;
    for(int i=2;i<=n-1;i++)
    {
        C[0]=0;
        for(int j=i;j>=1;j--)
        {
            C[j]=(C[j-1]+C[j])%MOD;
        }
    }

    g<<C[p-1];
    f.close();
    g.close();
    return 0;
}