#include<fstream>
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int i,j,n,k,n2,x,c[5010][5010];
int main(){
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>x;
    n2=(n-1)%(k-1)+1;
    c[0][0]=1;
    for(i=1;i<=n-1;i++)
        for(j=0;j<=i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%2000003;
    fout<<c[n-1][n2-1];


    return 0;
}