#include <iostream>
#include <cmath>
using namespace std;

long long mod = 1000003;

//最小２乗法
long long my_pow(int x,long long a) {
	long long temp = 1;
	if (a > 0) {
		temp = my_pow(x, a / 2);
		if (a % 2 == 0) { temp = (temp*temp) % mod; }
		else { temp = (((temp*temp) % mod)*x) % mod; }
	}
	return temp;
}

int main() {
	cin.tie(0);ios::sync_with_stdio(false);
	int x, N; cin >> x >> N;
	long long ans = 0;
	for (int i = 0; i < N;i++) {
		long long a; cin >> a;
		ans += my_pow(x, a);
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}