#include <iostream>
using namespace std;
typedef long long ll;
const int mod=1000003;
int main(){
  ll x,N;cin>>x>>N;
  ll a;
  ll c=0;
  for(ll i=0;i<N;++i){
    cin>>a;
    ll b=1;
    for(ll j=0;j<a;++j){
      b%=mod;
      b*=x;
      b%=mod;
    }
    c%=mod;
    b%=mod;
    c+=b;
    c%=mod;
  }
  cout<<c<<endl;
}