#include<fstream>
# define baza 2000003
using namespace std;
int n, k, i, j, var, p, pas[5003];
ifstream in("sandokan.in");
ofstream out("sandokan.out");
int main(){
    in>>n>>k;
    for(i=n; i--;)
        in>>var;
    p=n%(k-1);
    if(p==0)
        p=k-1;
    p--;
    pas[0]=1;
    for(i=1; i<=n-1; i++){
        pas[0]=1;
        for(j=i; j>=1; j--)
            pas[j]=(pas[j-1]+pas[j])%baza;
    }
    out<<pas[p];
return 0;
}