#include <bits/stdc++.h>
#define MOD 1000003
using namespace std;
ifstream f("grigo.in");
ofstream g("grigo.out");
int fr[1005],v[100005],sol[10005],fr2[100005],n,m,i,nr;
void back1(int k)
{
    if (k>n)
    {
        int i,j,ok1=0;
        ok1=1;
        for (i=1;i<=n;i++)
        {
            int ok=1;
            for (j=i-1;j>=1;j--)
            {
                if (sol[i]<sol[j])
                {
                    ok=0;
                    break;
                }
            }
            if (fr[i]!=ok)
            {
                ok1=0;
                break;
            }
        }
        nr+=ok1;
    }
    else
    {
        for (int i=1;i<=n;i++)
        {
            if (fr2[i]==0)
            {
                sol[k]=i;
                fr2[i]=1;
                back1(k+1);
                fr2[i]=0;
                sol[k]=0;
            }
        }
    }
}
long long ridput (long long a,long long b)
{
    if (b==0)
    {
        return 1;
    }
    long long rez=ridput(a,b/2);
    if (b%2==0)
    {
        return (rez*rez)%MOD;
    }
    return ((rez*rez)%MOD*a)%MOD;
}
long long p;
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>v[i];
        fr[v[i]]=1;
    }
    sort (v+1,v+m+1);
    if (v[1]!=1)
    {
        g<<"0";
        return 0;
    }
    p=1;
    for (i=1;i<=n-1;i++)
    {
        p=(p*i)%MOD;
    }
    for (i=2;i<=m;i++)
    {
        p=(p*ridput(v[i]-1,MOD-2))%MOD;
    }
    g<<p;
    return 0;
}