#include using namespace std; typedef long long ll; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define req(i,n) for(int i = 1;i <= n; i++) #define rrep(i,n) for(ll i = n-1;i >= 0;i--) #define ALL(obj) begin(obj), end(obj) #define RALL(a) rbegin(a),rend(a) typedef long long int ll; typedef long double ld; const int MAX = 510000; const ll MOD = 1000000007; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const ll INF = 1e18; ll mod_pow(ll x, ll n, ll mod){ ll res = 1; while(n > 0){ if(n & 1) res = res*x%mod; x = x*x%mod;n >>= 1; }return res; } int main(){ int x,n,a;ll sum = 0;cin >>x >>n; rep(i,n){ cin >>a; sum += mod_pow(x,a,1000003); sum%=1000003; }cout << sum << endl; }