int v(const void*a,const void*b){return*(int *)b-*(int *)a;}

int main(){
int a[100],i,c,n,s,t,j;
scanf("%d%d",&c,&n);
for(i=0;~scanf("%d",a+i);i++);
qsort(a,n,4,v);
for(t=0,i=a[0],j=0;i+1;i--){
t=t*c%1000003;if(a[j]==i)t++,j++;
}
printf("%d",t);
return 0;
}