#include typedef long long ll; using namespace std; const int INF = 1e9; const int MOD = 1e9+7; const ll LINF = 1e18; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) for(int i=0;i<(n);++i) #define REPR(i,n) for(int i=n;i>=0;i--) #define ALL(v) (v.begin(),v.end()) #define COUT(x) cout<<(x)<<'\n' template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } //二条累乗法 ll binpow(ll z,ll y){//xは変数,yは累乗 ll num = 1; while(y!=0){ if(y%2==0){ z*=z; y/=2; if(z>1000003)z%=1000003; } else{ num*=z;y--; } if(num>1000003)num%=1000003; } return num; } int main(){ int x,n,a; cin >> x >> n; ll ans = 0; REP(i,n){ cin >> a; ans += binpow(x,a); if(ans>1000003)ans%=1000003; } COUT(ans); return 0; }