#include using namespace std; #if __has_include() #include using namespace atcoder; using mint = modint998244353; #endif using ll = long long; using ld = long double; const ll INF = 1ll<<60; const ld EPS = 1.0/1e9; #define endl "\n" #define rep(i,a,b) for(int i=a;i=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() #define del(x) sort(all(x)); x.erase(unique(all(x)),x.end()); ll pw[40]; ll pw_md(ll x){ ll res=1; ll cnt=0; while(x){ if(x%2==1){ res*=(pw[cnt+1]); res%=1000003; } cnt++; x/=2; } return res; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll x,n; cin >> x >> n; pw[0]=1; pw[1]=x; rep(i,1,39){ pw[i+1]=(pw[i]*pw[i])%1000003; } ll ans=0; rep(i,0,n){ ll a; cin >> a; ans+=pw_md(a); ans%=1000003; } cout << ans << endl; }