#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);cin.tie(0);//cinとcoutを切り離し高速化
  long long x,N;
  cin>>x>>N;
  long long sum=1;
  long long sumf=0;
  long long NN[N];
  for (int i = 0; i < N; ++i) {
	  cin>>NN[i];
	  for (int var = 0; var < NN[i]; ++var) {
		  sum=sum*x;
		  if(sum>1000003){
			  sum=sum%1000003;
		  }
	  }
	  sumf=sumf+sum;
	  sum=1;
  }
  printf("%lld",sumf);
}