#include <bits/stdc++.h>
#include <math.h>

using namespace std;

#ifndef ONLINE_JUDGE
	#define _GLIBCXX_DEBUG
	#define local_shit freopen("inp.txt", "r", stdin);
#else
  #define local_shit
#endif

// io macros
#define fastio ios::sync_with_stdio(false); cin.tie(nullptr);
#define make_test_shit freopen("inp.txt", "w", stdout);

// c++ short types
#define Int long long
#define vt vector
#define pi pair<int, int>

// code macros
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ins insert
#define mp make_pair

// loops macros
#define each(x, a) for(auto &x: a)

// some functions
template<typename T>
void umax(T &a, const T &b) { a = max(a,b); }
template<typename T>
void umin(T &a, const T &b) { a = min(a,b); }
void whattime() { cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; }
template<typename T>
T firsttrue(T l, T r, function<bool(T)> f) {
	while(r - l > 1) {
		T m = (l+r)/2;
		if(f(m)) {
			r = m;
		} else {
			l = m;
		}
	}
	return r;
}
template<typename T>
T lasttrue(T l, T r, function<bool(T)> f) {
	while(r - l > 1) {
		T m = (l+r)/2;
		if(f(m)) {
			l = m;
		} else {
			r = m;
		}
	}
	return l;
}

const int mod = 1e6+3;
void add(int &a, int b) {
	a += b;
	if(a >= mod) {
		a -= mod;
	}
	if(a < 0) {
		a += mod;
	}
}
int mul(int a, int b) {
	return (a*1ll*b) % mod;
}
int bin_pow(int base, int power) {
	int r = 1;
	for(; power; power >>= 1, base = mul(base, base)) {
		if(power & 1) {
			r = mul(r, base);
		}
	}
	return r;
}
int inv(int x) {
	return bin_pow(x, mod-2);
}

const int nmax = 1e6+100;
int fact[nmax], invfact[nmax];

void precalc() {
	fact[0] = invfact[0] = 1;
	for(int i = 1; i < nmax; ++i) {
		fact[i] = mul(fact[i-1], i);
		invfact[i] = inv(fact[i]);
	}
}
int cnk(int k, int n) {
	if(k > n) {
		return 0;
	}
	return mul(fact[n], mul(invfact[n-k], invfact[k]));
}

int n, k;
int s[nmax], a[nmax];
void read() {
	cin >> n >> k;
	for(int i = 0; i  + k - 1 < n; ++i) {
		cin >> a[i];
	}
}

void smart() {
	fill(s, s + n, -1);
	bool flag = true;
	for(int i = 0; (i + k - 1) + 1 < n; ++i) {
		flag = flag && abs(a[i]-a[i+1]) <= 1;
		if(a[i] < a[i+1]) {
			s[i] = 0; s[i+k] = 1;
		} else if(a[i] > a[i+1]) {
			s[i] = 1; s[i+k] = 0;
		}
	}
	if(not flag) {
		cout << "0\n";
		return ;
	}
	for(int i = 0; i < k; ++i) {
		for(int j = i; j < n; j += k) {
			int l = j;
			while(l < n && s[l] == -1) {
				l += k;
			}
			if(l < n) {
				while(j < l) {
					s[j] = s[l]; j += k;
				}
			}
			j = l;
		}
	}
	int free = 0, sum = a[0];
	for(int i = 0; i < k; ++i) {
		free += s[i] == -1;
		sum -= s[i] == 1;
	}
	cout << cnk(sum, free) << endl;
}

void solver() {
	precalc();
	read();
	smart();
}

int main()
{
	fastio;
//	local_shit;
	int tt = 1; //cin >> tt;
	while(tt--) {
		solver();
	}
}