#include <cstdio>

const int maxn = 5004;
const int mod  = 2000003;

FILE *in = fopen("sandokan.in","r"), *out = fopen("sandokan.out","w");

int n, k;
int a[maxn];

void read()
{
    fscanf(in, "%d %d", &n, &k);

    for ( int i = 1; i <= n; ++i )
        fscanf(in, "%d", &a[i]);
}

int c1[maxn];
int c2[maxn];
void combo()
{
    k = n % k;

    for ( int i = 1; i <= n; ++i )
    {
        c1[0] = 1;
        c1[1] = i;

        for ( int j = 2; j <= k; ++j )
            c1[j] = c2[j-1] + c2[j];

        for ( int j = 1; j <= k; ++j )
            c2[j] = c1[j] % mod;
    }
}

int main()
{
    read();

    combo();

    fprintf(out, "%d\n", c1[k]);

    return 0;
}