#include <fstream>
#define mod 2000003

using namespace std;

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

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

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