#include<stdio.h>
const int MOD=1000003;
long long int f(long long int x,int a){
	long long int res=1;
	while(a>0){
		if((a%2)==1){
			res=(res*x)%MOD;
		}
		x=(x*x)%MOD;
		a/=2;
	}
	return res%MOD;
}

int main(){
	long long int x,ans=0;
	int n,a;
	scanf("%lld %d",&x,&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a);
		ans=(ans+f(x,a))%MOD;
	}
	printf("%lld\n",ans);
}