#include<iostream>
using namespace std;
typedef long long LL;
const int mod = 1000003;
LL powmod(LL x, int e){
	LL r = 1;
	while (e){
		if (e&1) r = (r*x) % mod;
		x = (x*x) % mod;
		e >>= 1;
	}
	return r;
}
int main(){
	LL x; int n;
	cin >> x >> n;
	LL ans = 0;
	for (int i = 0; i < n; i++){
		int a; cin >> a;
		ans += powmod(x, a);
	}
	ans %= mod;
	cout << ans << endl;
	return 0;
}