#include <bits/stdc++.h>
#define mod 2000003
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int f[5002];
int v[5002];
void euclid(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1;
        y = 0;
        return;
    }
    int x0,y0;
    euclid(b,a % b,x0,y0);
    x = y0;
    y = x0 - (a / b) * y0;
}
int invmod(int n){
    int x,y;
    euclid(mod,n,x,y);
    return (y % mod + mod) % mod;
}
void genf(int n){
    f[0] = f[1] = 1;
    for(int i = 2; i <= n; i++) f[i] = (1LL * f[i - 1] * i) % mod;
}
int comb(int n, int k){
    return (1LL * f[n] % mod * invmod(f[k]) % mod * invmod(f[n - k])) % mod;
}
int main()
{
    int n,k,i,t;
    fin >> n >> k;
    genf(n);
    for(i = 1; i <= n; i++){
        fin >> v[i];
    }
    t = n % (k - 1);
    if(t == 0) t = k - 1;
    fout << comb(n - 1,t - 1);
    return 0;
}