#include <stdio.h>
#include <assert.h>
#include <algorithm>

using namespace std;

#define MOD 2000003
#define aduna(x, y) (((x += y) >= MOD) ? (x -= MOD) : (0))

int N, K, P, v[5005], Comb[2][5005];

int main(void)
{
        int i, j, crt = 0, prev = 1;
        
        freopen("sandokan.in", "r", stdin);
        freopen("sandokan.out", "w", stdout);

        scanf("%d %d", &N, &K);
	assert(2 <= K && K <= N && N <= 5000);
        for (i = 1; i <= N; ++i)
	{
                scanf("%d", &v[i]);
		assert(1 <= v[i] && v[i] <= 2000000000);
	}
        sort(v+1, v+N+1);
        for (i = 1; i < N; ++i)
                if (v[i] == v[i+1])
                        for (;;);

        P = N % (K-1);
        if (!P) P = K-1;

        Comb[0][0] = 1;
        for (i = 1; i < N; ++i)
        {
                crt = (i & 1); prev = !crt;
                for (j = 0; j <= i; ++j)
                {
                        (!j) ? (Comb[crt][0] = 0) : (Comb[crt][j] = Comb[prev][j-1]);
                        aduna(Comb[crt][j], Comb[prev][j]);
                }
        }
        printf("%d\n", Comb[crt][P-1]);

        return 0;
}