#include <bits/stdc++.h>
using namespace std;
long long bn[32];
int main(){
	long long x;
	cin >> x;
	bn[0] = x;
	for(int i = 1 ; i <= 31 ; i++)
		bn[i] = (bn[i-1] * bn[i-1]) % 1000003;
	int N;
	cin >> N;
	long long res = 0;
	for(int i = 0 ; i < N ; i++){
		int a;
		cin >> a;
		long long tot = 1;
		for(int j = 0 ; j < 32 ; j++)
			if( a >> j & 1 ) {
				tot = tot * bn[j] % 1000003;
			}
		res += tot;
		res %= 1000003;
	}
	cout << res << endl;
	
}