#include <bits/stdc++.h>
using namespace std;

int main(){
	int x,N,maxi=0;
	cin>>x>>N;
	int a[N];
	long long int dp[100000004],sum=0;
	dp[0]=1;
	
	for(int i=0;i<N;i++){
		cin>>a[i];
		maxi=max(maxi,a[i]);
	}
	
	for(int i=1;i<=maxi;i++){
		dp[i]=(dp[i-1]*x)%1000003;
	}
	
	for(int i=0;i<N;i++){
		sum+=dp[a[i]];
		sum%=1000003;
	}
	cout<<sum<<endl;
	return 0;	
}