#include <iostream>
using namespace std;
typedef long long ll;
const int mod=1e6+3;
int main(){
  ll x,n,a,b,y,z;
  cin>>x>>n;
  b=0;
  y=x;
  for(int i=0; i<n; ++i){
    cin>>a;
    z=1;
    for(ll j=1; j<=a; ++j){
      z%=mod;
      z*=y;
    }
    z%=mod;

    b+=z;
  }
  cout<<b<<endl;
  return 0;
}