#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define ll long long
#define LCBorz ios_base::sync_with_stdio(false);cin.tie(0);
const int N=1000005;
const int mod=1e6+3;
vector<ll> fac(N),inv(N);
ll pw(ll a,int b){
ll ans=1;
while(b>0){
if(b&1)ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
int32_t main(){
LCBorz;
fac[0]=inv[0]=1;
for(int i=1;i<N;i++){
fac[i]=fac[i-1]*i%mod;
inv[i]=pw(fac[i],mod-2);
}
int n,m;cin>>n>>m;
int p=n-m+1;
vector<int> v(p);
for(int i=0;i<p;i++){
cin>>v[i];
if(v[i]>m){
cout<<0<<endl;
return 0;
}
}
vector<int> ans(n,-1),vis(n,0);
auto upd=[&](int i,int j){
if(ans[i]==-1){
ans[i]=j;
}
else if(ans[i]!=j){
cout<<0<<endl;
exit(0);
}
};
vector<int> adj[N];
auto dfs=[&](auto dfs1,int k,int pa,int val)->void {
vis[k]=1;
upd(k,val);
for(int j:adj[k]){
if(j==pa)continue;
dfs1(dfs1,j,k,val);
}
};
for(int i=0;i<p-1;i++){
if(abs(v[i]-v[i+1])>1){
cout<<0<<endl;
return 0;
}
if(v[i]==v[i+1]+1){
upd(i,1);
upd(i+m,0);
}
else if(v[i]==v[i+1]-1){
upd(i,0);
upd(i+m,1);
}
else{
adj[i].push_back(i+m);
adj[i+m].push_back(i);
}
}
for(int i=0;i<n;i++){
if(ans[i]!=-1&&vis[i]==0){
dfs(dfs,i,i,ans[i]);
}
}
int a=0,b=v[0];
for(int i=0;i<m;i++){
if(ans[i]==-1){
a++;
}
if(ans[i]==1){
b--;
}
}
if(b>a||b<0){
cout<<0<<endl;
return 0;
}
cout<<fac[a]*inv[b]%mod*inv[a-b]%mod<<endl;
return 0;
}
