#include <iostream>
using namespace std;
typedef long long int ll;
#define E 1000003

ll fac(ll a,ll b){//a^bを計算
	ll ans=1;
	while(b){
		if(b&1)	ans=(ans*a)%E;
		a=(a*a)%E;
		b>>=1;
	}
	return ans;
}

int main(){
	int x,n;	cin>>x>>n;
	ll ans=0;
	int a;
	for(int i=0;i<n;i++){
		cin>>a;
		ans=(ans+fac(x,a))%E;
	}
	cout<<ans<<endl;
	return 0;
}