#include <bitset>
#include <cstdio>
 
using namespace std;
 
bitset <100000> v(0);
 
int main()
{
    long long n,m,i,x,sol;
    freopen("grigo.in","r",stdin);
    freopen("grigo.out","w",stdout);
    scanf("%lld %lld",&n,&m);
    for (i=1;i<=m;++i)
    {
        scanf("%lld",&x);
        v[x-1]=1;
    }
    for (i=0,sol=1;i<n;++i)
        if (!v[i])
            sol=sol*(i)%1000003;
    printf("%lld\n",sol);
    return 0;
}