#include <fstream>
#define mod 2000003

using namespace std;

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

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

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