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

long long pow_mod(long long a, int p){
	if (p==0) return 1;
	if (p%2){
		return a*pow_mod(a, p-1)%mod;
	}
	long long b = pow_mod(a, p/2);
	return b*b%mod;
}
int main(){
	int x,N;
	cin>>x>>N;
	int a;
	long long int sum=0;
	
	for(int i=0;i<N;i++){
		cin>>a;
		sum+=pow_mod(x,a);
	}
	sum%=1000003;
	
	cout<<sum<<endl;
	return 0;	
}