#include <bits/stdc++.h>
using namespace std;
#define MOD 1000003
int64_t powmod(int64_t a, int64_t p) {
	int64_t value = 1;
	for(int64_t mul = a; p > 0; p >>= 1, mul = (mul * mul) % MOD) {
		if(p & 1) value = (value * mul) % MOD;
	}
	return value;
}

int main() {
	int64_t x, N, a;
	cin >> x >> N;
	int64_t S = 0;
	for(int i = 0; i < N; i++) {
		cin >> a;
		S = (S + powmod(x, a)) % MOD;
	}
	cout << S << endl;
	return 0;
}