#include<cstdio>
using namespace std;
long i,j,n,m,im[100001],x,xm,c[1000][1000];
int main()
{       freopen("grigo.in","r",stdin);
        freopen("grigo.out","w",stdout);
        scanf("%ld%ld",&n,&m);
        for(i=1;i<=m;i++)
        {       scanf("%ld",&x);
                im[x]=1;
        }
        if(!im[1])
        {       printf("0");
                return 0;
        }
        else
        {       c[0][1]=1;;
	        for(i=1;i<=n;i++)
		        for(j=1;j<=n-m+1;j++)
			        c[i][j]=c[i-1][j-1]+c[i-1][j];
                printf("%ld",c[n][n-m+1]%1000003);
                return 0;
        }
}