#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1000003;

ll xp[30];

int main(void) {
	int N;
	cin >> xp[0] >> N;
	
	for(int i = 1; i < 30; ++i) xp[i] = (xp[i - 1] * xp[i - 1]) % mod;
	
	ll ans = 0;
	for(int i = 0; i < N; ++i) {
		int A;
		cin >> A;
		ll r = 1;
		for(auto it = xp; A != 0; it ++, A >>= 1) if(A & 1) r = (r * (*it)) % mod;
		ans += r;
		if(ans >= mod) ans -= mod;
	}
	cout << ans << endl;
	return 0;
}