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

const int BIG = 1000003;
long pow(long n, int r){
	if(r==0) return  1;
	if(r%2 == 0) return pow((n*n)%BIG, r/2);
	else return (n*pow(n, r-1))%BIG;
}
	

int main(){
	int x, n;
	cin >> x >> n;
	vector<int> v(n);
	for(int i=0; i<n; i++)cin >> v[i];

	long sum =0;
	for(int i=0; i<n; i++){
		sum += pow(x, v[i]);
		sum = sum % BIG;
		//cout << pow(x, v[i]) << endl;
	}
	
	cout << sum << endl;
}