#include <cstdio>
#include <cstring>
using namespace std;

#define MAXN 5002
#define MOD 2000003

int C[2][MAXN], N, K, P;

int main(void)
{
    freopen("sandokan.in", "rt", stdin);
    freopen("sandokan.out", "wt", stdout);
    
    int i, j, k, x, prev, crt;

    scanf("%d %d\n", &N, &K); for(i = 1; i <= N; i++) scanf("%d ", &x);

    if(K == 1) { printf("%d\n", N); return 0; }
    
    for(P = N; P >= K; P = P-K+1) ;

    for(prev = 0, crt = 1, i = 1; i <= N-1; i++)
    {
        for(C[crt][0] = C[crt][i] = 1, j = 1; j < i; j++)
            C[crt][j] = C[prev][j] + C[prev][j-1], C[crt][j] %= MOD;
        prev ^= 1, crt ^= 1;
    }

    printf("%d\n", C[prev][P-1]);

    return 0;
}