#include <stdio.h>

long long p;
int i,N,K,a[5000],max;

int main()
{
  freopen("sandokan.in","r",stdin);
  freopen("sandokan.out","w",stdout);
  scanf("%d %d",&N,&K);
  max=0;
  for (i=1;i<=K;++i)
       {
	scanf("%d", &a[i]);
	if (a[i]>max)
	    max=a[i];
       }
  p=1;
  K=max;
  for (i=N-(N%(K-1))+1;i<N;++i)
       p=(p*i)%2000003;
  for (i=2;i<(N%(K-1));++i)
       p=(p/i)%2000003;
  printf("%lld",p%2000003);
  return 0;
}