#include<iostream>
#include<algorithm>

using namespace std;

#define NMAX 100
#define MOD 1000003

int main(){

	int x,N;
	int cnt=0;
	long long a[NMAX];
	long long ans=0;
	long long xa=1;
	long long xc=0;
	cin>>x;
	cin>>N;
	for(int i=0;i<N;i++) cin>>a[i];

	sort(a,a+N);

	while(cnt<N){
		while(cnt<N&&a[cnt]==xc){
			ans+=xa;
			ans%=MOD;
			cnt++;
		}
		xa*=x;
		xa%=MOD;
		xc++;
	}
	cout<<ans<<endl;
}