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

int main() {
    ifstream fin("sandokan.in");
    ofstream fout("sandokan.out");
    fin>>n>>k;
    for (i=1;i<=n;i++) {
        fin>>a[i];
    }
    c[0]=1;
    for (i=1;i<=n;i++) {
        for (j=i;j>=1;j--) {
            c[i]=(c[i]+c[i-1])%mod;
        }
    }
    fout<<c[k%n];
    return 0;
}