#include <bits/stdc++.h>
using namespace std;

const int mod = 1000003;

long long xp[mod - 1];

int main(void) {
	int x, N;
	cin >> x >> N;
	
	xp[0] = 1;
	for(int i = 1; i < mod - 1; ++i) xp[i] = (xp[i - 1] * x) % mod;
	
	vector<int> A(N);
	for(int i = 0; i < N; ++i) cin >> A[i];
	
	long long ans = 0;
	for(int i = 0; i < N; ++ i) ans = (ans + xp[A[i] % (mod - 1)]) % mod;
	cout << ans << endl;
	return 0;
}