#include <cstdio>
#include <algorithm>
#include <vector>

#define int long long

#define For(i, l, r) for(int i = l; i <= r; i ++)

using namespace std;

void in(int &x)
{
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	for(x = 0; c >= '0' && c <= '9'; c = getchar())
		x = x * 10 + c - '0';
}

const int N = 1e6 + 50, P = 1000003;

int n, m, fac[N], inv[N], sum[N], K, fa[N], lim[N];

int C(int n, int m)
{
	if(n < m) return 0;
	return fac[n] * inv[m] % P * inv[n - m] % P;
}

int ksm(int x, int y)
{
	int s = 1;
	while(y)
	{
		if(y & 1) s = s * x % P;
		x = x * x % P; y >>= 1;
	}
	return s;
}

int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
int dai[N];

signed main()
{
	// freopen("bit.in", "r", stdin);
	// freopen("bit.out", "w", stdout);
	in(n); in(K);
	For(i, 1, n - K + 1) in(sum[i]);
	For(i, 1, n) lim[i] = -1, dai[i] = -1, fa[i] = i;
	fac[0] = inv[0] = 1;
	For(i, 1, n) fac[i] = fac[i - 1] * i % P;
	inv[n] = ksm(fac[n], P - 2);
	for(int i = n; i ; i --) inv[i - 1] = inv[i] * i % P;
	For(i, 1, n - K + 1)
		if(sum[i] > K) {puts("0"); return 0;}
	For(i, 1, n - K)
		if(sum[i + 1] == sum[i])
		{
			fa[find(i + K)] = find(i);
		}
		else
		{
			if(abs(sum[i + 1] - sum[i]) > 1)
			{
				puts("0"); return 0;
			}
			if(sum[i + 1] > sum[i]) lim[i + K] = 1, lim[i] = 0;
			else lim[i + K] = 0, lim[i] = 1;
		}
	For(i, 1, n) if(lim[i] != -1)
	{
		if(dai[find(i)] == -1) dai[find(i)] = lim[i];
		else if(dai[find(i)] != lim[i]) {puts("0"); return 0;}
	}
	For(i, 1, n) lim[i] = dai[find(i)];
	int all = K, res = sum[1];
	For(i, 1, K) if(lim[i] != -1) all --, res -= lim[i];
	printf("%lld\n", C(all, res));
	return 0;
}