#include <fstream>
#define dim 5010
#define mod 2000003
using namespace std;
int a[dim];
int c[dim];
int i,j,k,n,x;

int main() {
    ifstream fin("sandokan.in");
    ofstream fout("sandokan.out");
    fin>>n>>k;
    for (i=1;i<=n;i++) {
        fin>>a[i];
    }
    x=n;
    while (x>=k) {
        x-=k;
    }
    x--;
    n--;
    c[0]=1;
    for (i=1;i<=n;i++) {
        for (j=i;j>=1;j--) {
            c[j]=(c[j]+c[j-1])%mod;
        }
    }
  //  for (i=0;i<=n-1;i++) fout<<c[i]<<" ";
   // fout<<"\n";
    ///rezultatul este Combinari de n-1 luate cate x
    ///deoarece mereu o sa fie inclus maximul din sir
    fout<<(c[x])%mod;
    return 0;
}