#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using db = long double;
const ll MOD=1e6+3;
int main()
{
int n,k;cin>>n>>k;
int sz=k;
vector<int> vis(n+1,0),arr(n-k+2,-1),s(n+1,-1);
int cur=sz,cnt=0;
for (int i=0;i<n-k+1;i++){
cin >> arr[i];
}
for (int i=0;i<n-k;i++){
if (arr[i]==arr[i+1] && s[cur-sz]==-1){
cnt++;
}else if (arr[i]==arr[i+1] && s[cur-sz]!=-1){
s[cur]=s[cur-sz];vis[cur-sz]=1;
}
else if (arr[i]<arr[i+1]){
s[cur-sz]=0;s[cur]=1;vis[cur-sz]=1;
}else{
s[cur-sz]=1;s[cur]=0;vis[cur-sz]=1;
}
//j-th element are known (either 1,0 0,1 or thr same)
cur++;
}
/*
for (int i=0;i<=n;i++){
cout<<s[i]<<" ";
}
*/
for (int i=0;i<sz;i++){
if (vis[i]) cnt++; // if unknown, it could be anything.
}
// we'll got that s1+s2+...+sk == arr[0]-curretn known bits
// for every unknow bits, choose the one that satisfied the condition.
// which is C(k,arr[0]-sum(a1,...,ak))
// the problrm is to check if the condition stays the same for all i...
// fuck it.
int x=cnt,y=arr[0];
for (int i=0;i<sz;i++){
if (s[i]==1) y--;
}
if(y<0||y>x){
cout<<0;return 0;
}
if (y>x-y)y=x-y;
//cout << x << " " << y << "\n";
ll res=1;
for (int i=1;i<=y;i++){
res = res * (x-i+1) / i;
res%=MOD;
}cout << res;
return 0;
}
