#include <fstream>
#define mod 2000003

using namespace std;

ifstream fin("sandokan.in");
ofstream fout("sandokan.out");

int c[5001], x;
short n, k, i;
long long sol = 1;

int main(){
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>x;
    i = 1;
    c[0] = 1;
    while(i <= n){
        for(x=i;x>0;x--)
            c[x] = (c[x]+c[x-1])%mod;
        if((n-i)%(k-1) == 0 && k <= i)
            sol = (sol*c[k])%mod;
        i++;
    }

    fout<<sol;
    return 0;
}