#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000003
ll power(ll x, ll n)
{
ll res = 1;
x %= MOD;
while (n)
{
if (n & 1)
res = (res * x) % MOD;
x = (x * x) % MOD;
n >>= 1;
}
return res;
}
void solve()
{
ll n, k, c0 = 0, c1 = 0, ans = 1;
cin >> n >> k;
vector<ll> a(n - k + 1), b(n, -1);
for (int i = 0; i < n - k + 1; i++)
{
cin >> a[i];
if (i)
{
if (a[i] < a[i - 1])
{
b[i - 1] = 1;
b[i + k - 1] = 0;
}
else if (a[i] > a[i - 1])
{
b[i - 1] = 0;
b[i + k - 1] = 1;
}
}
}
for (ll i = n - 1; i >= 0; i--)
{
if (i >= k)
{
if (b[i] != -1 and b[i - k] == -1)
{
b[i - k] = b[i];
}
}
else
{
c1 += b[i] == 1;
c0 += b[i] == 0;
}
}
for (ll i = 1; i <= a[0] - c1; i++)
{
ans = (((ans * power(i, MOD - 2)) % MOD) * (k - c1 - c0 - i + 1)) % MOD;
}
cout << ans << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t = 1;
// cin >> t;
for (int i = 1; i <= t; i++)
{
solve();
}
}
