#include <iostream>
#include <cmath>
using namespace std;

#define MOD 1000003

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int x, n, a, x_t, total=0;
  
  cin >> x >> n;
  for(int i=0; i<n; ++i){
    x_t=x;
    cin >> a;
    if(a==0){
      total+=1;
      continue;
    }
    for(int j=1; j<a; ++j){
      x_t*=x;
      x_t%=MOD;
    }
    total+=x_t;
  }

  cout << total << "\n";

  return 0;
}