#include <fstream>
#define MOD 2000003
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int n,k,i,j,c[5005],v[5005];
int main(){
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>v[i];
    k=(n-1)%(k-1);
    c[1]=1;
    for(i=2;i<=n;i++)
        for(j=i;j>=1;j--)
            c[j]=(c[j]+c[j-1])%MOD;
    fout<<c[k+1]%MOD;
    return 0;
}