#include<fstream>
#include<vector>
#include<iostream>
#define DN 100005
#define M 1000003
#define x first
#define y second
#define pb push_back
using namespace std;
ifstream fin("grigo.in");
ofstream fout("grigo.out");
int n,m,a[DN],l,f[DN],dp[DN],c;
int ve(int a,int b)
{
    int c=a,r=1,put=1;
    while(put<=b)
    {
        if(put&b)
            r=(1LL*r*c)%M;
        put=put*2;
        c=(1LL*c*c)%M;
    }
    return r;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>a[i];
    f[0]=1;
    for(int i=1;i<DN;i++)
        f[i]=(1LL*f[i-1]*i)%M;
    m++;
    a[m]=n+1;
    for(int i=1;i<=m;i++)
    {
        if(i==1)
        {
            dp[i]=f[a[i]-1];
            continue;
        }
        l=a[i]-a[i-1]-1;
        dp[i]=f[l];
        c=(1LL*f[a[i]-1]*ve(f[a[i-1]],M-2))%M;
        c=(1LL*c*ve(f[a[i]-1-a[i-1]],M-2))%M;
        if(i==m)
        {
            c=(1LL*f[a[i]-2]*ve(f[a[i-1]-1],M-2))%M;
            c=(1LL*c*ve(f[a[i]-1-a[i-1]],M-2))%M;
        }
        dp[i]=(1LL*dp[i]*c)%M;
    }
    fout<<dp[m];
}