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

const int Mod = 1000003;

long long PowMod(int radix, int index) {
	long long ret = 1;
	for (int i = 1; i <= index; i++) {
		ret = ret * radix % Mod;
	}

	return ret;
}


int main() {
	int x, n;
	cin >> x >> n;

	long long sum = 0;
	for (int i = 0; i < n; i++) {
		int index;
		cin >> index;
		sum += PowMod(x, index);
	}

	cout << sum % Mod << endl;

	system("pause");

	return 0;
}