#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MOD=1'000'003;
ll add(ll a,ll b){return (a+b)%MOD;}
ll mdpw(ll a,ll b){
    ll ret=1;
    a%=MOD;
    while(b){
        if(b&1)ret=(ret*a)%MOD;
        a=(a*a)%MOD;b>>=1;
    }
    return ret;
}
void solve(){
    ll x;int n;cin>>x>>n;
    int ans=0;
    for(int i=0,e;i<n;++i){
        cin>>e;
        ans=add(ans,mdpw(x,e));
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int T=1; //cin>>T;
    while(T--)solve();
    return 0;
}