#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
const ll MOD = 1e6 + 3;
ll jc[N], jc_inv[N];
int n, k, a[N], d[N];

ll power(ll a, ll b)
{
	ll c = 1;
	while(b)
	{
		if(b & 1) c = c * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return c;
}

ll C(ll n, ll m)
{
	if(n < 0 || m < 0 || n < m) return 0;
	return jc[n] * jc_inv[n - m] % MOD * jc_inv[m] % MOD;
}

int main()
{
	scanf("%d%d", &n, &k);
	jc[0] = 1;
	for(int i = 1; i <= n; i++) jc[i] = jc[i - 1] * i % MOD;
	jc_inv[n] = power(jc[n], MOD - 2);
	for(int i = n - 1; i >= 0; i--) jc_inv[i] = jc_inv[i + 1] * (i + 1) % MOD;
	for(int i = 0; i < n - k + 1; i++) scanf("%d", &a[i]);
	for(int i = 0; i < n - k; i++) d[i] = a[i + 1] - a[i];
	int s = a[0], cnt = k;
	for(int u = 0; u < k; u++)
	{
		int flag = 0;
		for(int p = u; p < n - k; p += k)
		{
			if(d[p] < 0)
			{
				if(d[p] != -1 || flag == -1)
				{
					puts("0");
					return 0;
				}
				else
				{
					flag = d[p];
				}
			}
			if(d[p] > 0)
			{
				if(d[p] != 1 || flag == 1)
				{
					puts("0");
					return 0;
				}
				else
				{
					flag = d[p];
				}
			}
		}
		if(flag == -1) s--, cnt--;
		if(flag == 1) cnt--;
	}
	printf("%lld\n", C(cnt, s));
	return 0;
}