#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("sandokan.in");
ofstream fout("sandokan.out");
int n,i,j,p,q,x;
int v[5005];
int main(){
    fin>>n>>p;
    for(i=1;i<=n;i++){
        fin>>x;
    }
    n--;
    p--;
    q=n%p;
	v[1]=1;
	for(i=2;i<=n+1;i++){
		for(j=i;j>=1;j--){
			v[j]=(v[j-1]+v[j])%2000003;
		}
	}
	fout<<v[q+1];
    return 0;
}