#include <bits/stdc++.h>
#define ll long long
#define MAXN 1000010
#define MOD 1000003
using namespace std;
ll a[MAXN],val[MAXN],fact[MAXN];
vector<ll> p[MAXN];
void Init()
{
fact[0]=1;
for (ll i=1;i<MAXN;i++)
fact[i]=(fact[i-1]*i)%MOD;
return;
}
ll Exp(ll n,ll k)
{
ll val[30];
val[0]=n;
for (ll i=1;i<30;i++)
val[i]=(val[i-1]*val[i-1])%MOD;
ll ans=1,cur=29;
while (k)
{
if ((1<<cur)<=k)
{
k-=(1<<cur);
ans=(ans*val[cur])%MOD;
}
cur--;
}
return ans;
}
ll Binomial_Coefficient(ll n,ll k)
{
return (((fact[n]*Exp(fact[k],MOD-2))%MOD)*Exp(fact[n-k],MOD-2))%MOD;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n,k;
cin >> n >> k;
for (ll i=1;i<=n-k+1;i++)
cin >> a[i];
if (k==1)
{
cout << 1;
return 0;
}
Init();
for (ll i=1;i<=n;i++)
val[i]=-1;
for (ll i=1;i<=k;i++)
p[i%k].push_back(i);
for (ll i=2;i<=n-k+1;i++)
{
if (a[i]==a[i-1])
val[i+k-1]=val[p[(i+k-1)%k].back()];
else if (a[i]>a[i-1])
{
val[i+k-1]=1;
val[p[(i+k-1)%k].back()]=0;
}
else
{
val[i+k-1]=0;
val[p[(i+k-1)%k].back()]=1;
}
p[(i+k-1)%k].push_back(i+k-1);
}
for (ll i=0;i<k;i++)
{
ll lastt=-1;
for (ll j=p[i].size()-1;j>=0;j--)
{
if (val[p[i][j]]==-1)
val[p[i][j]]=lastt;
else
lastt=val[p[i][j]];
}
}
ll sum=0,cnt=0;
for (ll i=1;i<=k;i++)
{
if (val[i]!=-1)
sum+=val[i];
else
cnt++;
}
cout << Binomial_Coefficient(cnt,a[1]-sum);
return 0;
}
