#include<stdio.h>
#include<math.h>
double temp=0;
int main(void){
int i,x,n,a;
scanf("%d %d",&x,&n);
for(i=0;i<n;i++){
  scanf("%d",&a);
  temp+=pow(x,a);
}
printf("%.lf\n",fmod(temp,1000003));
  return 0;
}