#include<stdio.h>
long long n,m,st,aa,i;
long long ua,a1;
int main()
{
 freopen("grigo.in","r",stdin);
 freopen("grigo.out","w",stdout);
 scanf("%lld%lld",&n,&m);
 st=1;
 ua=1;
 for(i=1;i<=m;++i)
    {scanf("%lld",&aa);
     for(st;st<aa;++st)
        {a1=(ua*(st-1))%1000003;
         ua=a1;}
     ++st;}
 for(st;st<=n;++st)
    {a1=(ua*(st-1))%1000003;
     ua=a1;}
 printf("%lld\n",a1);
 return 0;
}