#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; } int main(){ int x,n; cin >> x >> n; int num = x; vector vec(100000010,1); vec[1] = x; FOR(i,2,100000000){ num *= x; if(num>1000003) num %= 1000003; vec[i]=num; } int a; int ans = 0; REP(i,n){ cin >> a; ans += vec[a]; } COUT(ans%1000003); return 0; }