#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000010
const int mod=1e6+3;
int n,m,a[N],mark[N];
int fac[N],ifac[N];
int fa[N],col[N];

int read ()
{
	int k=1,s=0;char ch=getchar ();
	while (!isdigit (ch)) {if (ch=='-') k=-1;ch=getchar ();}
	while (isdigit (ch)) {s=s*10+ch-'0';ch=getchar ();}
	return k*s;
}

int Qpow (int x,int y)
{
	int res=1;
	while (y>0)
	{
		if (y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return res;
}

void Init ()
{
	n=read ();m=read ();
	fac[0]=fac[1]=1;
	for (int i=2;i<=n;i++)
		fac[i]=1ll*fac[i-1]*i%mod;
	ifac[n]=Qpow (fac[n],mod-2);
	for (int i=n-1;i>=0;i--)
		ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
	for (int i=1;i<=n-m+1;i++)
		a[i]=read ();
}

int Find (int x)
{
	return x==fa[x]?x:fa[x]=Find (fa[x]);
}

int GetCol (int i)
{
	return col[Find (i)];
}

void Merge (int x,int y)
{
	int rx=Find (x),ry=Find (y);
	if (rx!=ry)
	{
		col[rx]=max (col[rx],col[ry]);
		fa[ry]=rx;
	}
}

int Calc (int n,int m)
{
	if (m>n) return 0;
	if (m==n || n==0) return 1;
	return 1ll*fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}

void Work ()
{
	for (int i=1;i<=n;i++)
	{
		fa[i]=i;
		col[i]=-1;
	}
	for (int i=2;i<=n-m+1;i++)
	{
		int j=i+m-1;
		if (a[i]-a[i-1]==1)
		{
			if (GetCol (i-1)==0)
			{
				printf ("0\n");
				return;
			}
			col[Find (i-1)]=0;
			col[Find (j)]=1;
		}
		else if (a[i]-a[i-1]==-1)
		{
			if (GetCol (i-1)==1)
			{
				printf ("0\n");
				return;
			}
			col[Find (i-1)]=1;
			col[Find (j)]=0;
		}
		else if (a[i]==a[i-1])
		{
			int colA=GetCol (i-1);
			int colB=GetCol (j);
			if (colA==-1 || colB==-1 || colA==colB)
				Merge (i-1,j);
			else
			{
				printf ("0\n");
				return;
			}
		}
		else
		{
			printf ("0\n");
			return;
		}
	}
	int cntA=0,cntB=0;
	for (int i=1;i<=m;i++)
	{
		if (i!=Find (i)) continue;
		if (col[i]==1) cntA++;
		else if (col[i]==-1) cntB++;
	}
	printf ("%d\n",Calc (cntB,a[1]-cntA));
}

signed main ()
{
	Init ();
	Work ();
	return 0;
}