#include <stdio.h>
#define MOD 1000003
#define DIM 100005
#define ll long long
ll a[DIM];
short uz[DIM];
int n,m;
void read ()
{
    int i,nr;
    scanf ("%d",&n,&m);
    for (i=1; i<=m; ++i)
    {
        scanf ("%d",&nr);
        uz[nr]=1;
    }
}
void solve ()
{
    int i;
    a[1]=1;
    for (i=2; i<=n; ++i)
        if (uz[i])
            a[i]=a[i-1];
        else
            a[i]=(a[i-1]*(i-1))%MOD;
    printf ("%d",a[n]);
}
int main ()
{
    freopen ("grigo.in","r",stdin);
    freopen ("grigo.out","w",stdout);    
    read ();
    solve ();
    return 0;
}