#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e6 + 5;
const ll mod = 1e6 + 3;

int a[maxn], d[maxn];
ll fac[maxn], inv[maxn];

void precalc(int x)
{
	fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i <= x; i++)
	{
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = inv[mod % i] * (mod - mod / i) % mod;
	}
	for (int i = 2; i <= x; i++) inv[i] = inv[i] * inv[i - 1] % mod;
}

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	precalc(1000000);
	
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n - k + 1; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) d[i] = -1;
	for (int i = 1; i <= n - k; i++)
	{
		if (abs(a[i + 1] - a[i]) >= 2 || a[i] > k)
		{
			cout << 0;
			return 0;
		}
		
		if (a[i] != a[i + 1])
		{
			if (d[i] == (a[i] < a[i + 1]))
			{
				cout << 0;
				return 0;
			}
			
			int pos = i;
			while (pos > 0 && d[pos] == -1) d[pos] = (a[i] > a[i + 1]), pos -= k;
			d[i + k] = (a[i] < a[i + 1]);
		}
		else if (d[i] != -1) d[i + k] = d[i];
	}
	
	int cnt = 0, sum = a[1];
	for (int i = 1; i <= k; i++)
		if (d[i] == -1) cnt++;
		else sum -= d[i];
	
	cout << C(cnt, sum);
	return 0;
}