#include <iostream>
#include <vector>

using namespace std;

const long long MOD = 1000003LL;
long long powered[33] = { 1 };

long long power(int a) {
	long long result = 1LL;
	for (int i = 1; a > 0; ++i, a >>= 1) {
		if (a & 0x1) {
			result *= powered[i];
			result %= MOD;
		}
	}
	return result;
}

int main() {
	long long x;
	int n;
	cin >> x >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	powered[1] = x;
	for (int i = 2; i <= 32; ++i) {
		powered[i] = powered[i - 1] * powered[i - 1];
		powered[i] %= MOD;
	}
	long long result = 0LL;
	for (int i = 0; i < n; ++i) {
		result += power(a[i]);
		result %= MOD;
	}
	cout << result << endl;
	return 0;
}