#include <fstream>
#define R 2000003
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int n,i,j,t,k,p,v[5002],c[2][5002];
int main(){
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>v[i];
    p=n%(k-1);
    if(!p)p=k-1;
///dupa toate eliminarile va ramane sigur maximul din sir alaturi de oricare alte p-1 nr => comb de n-1 luate cate p-1
    n--; p--;
    c[1][0]=c[1][1]=1;
    for(i=2;i<=n;i++){
        c[t][0]=1;
        for(j=1;j<=i;j++)
            c[t][j]=(c[1-t][j-1]+c[1-t][j])%R;
        t=1-t;
    }
    fout<<c[1-t][p];
    return 0;
}