#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define mod 1000003

ll pmod(ll n, ll p){
	ll m=n%mod;
	if(p==0) return 1;
	ll rtn=pmod((m*m)%mod, p/2)%mod;
	if(p%2==1) rtn=rtn*m%mod;
	return rtn;
}

int main(){
	ll x, n;
	cin >> x >> n;
	ll ans=0;
	for(int i=0; i<n; i++){
		ll a;
		cin >> a;
		ans+=pmod(x, a);
		ans%=mod;
	}
	cout << ans << endl;
	return 0;
}