#include <bits/stdc++.h>
#define MOD 1000003
using namespace std;
ifstream f("grigo.in");
ofstream g("grigo.out");
int v[100005],n,m,i,nr;
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];
    }
    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;
}