#include <fstream>
#define mod 2000003

using namespace std;

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

int n, k, c[5001][5001], i, j, x;
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(j=1;j<=i && j<=k;j++)
            c[i][j] = (c[i-1][j] + c[i-1][j-1])%mod;
    }
    while(n >= k){
        sol = (sol * c[n][k])%mod;
        n -= k - 1;
    }
    fout<<sol;
    return 0;
}