#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using mint=modint;

int main(){
  mint::set_mod(1000003);
  ll n,x;cin>>x>>n;
  mint g=x,ans=0;
  vector<int> a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  for(int i=0;i<n;i++){
    ans+=g.pow(a[i]);
  }
  cout<<ans.val()<<endl;
}