#include <fstream>
#define mod 2000003

using namespace std;

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

int n, k, i, j, x;
long long sol = 1;

int c(int i, int j){
    if(i == 1)
        if(j == 0 || j == 1)
            return 1;
    int r = 0;
    if(i-1 >= j)
        r+= c(i-1, j);
    if(i-1 >= j-1)
        r+= c(i-1, j-1);
    return r%mod;
}

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