#include <iostream>
int main(){
	int64_t m=1'000'003;
	int64_t x,N,sum=0;
	std::cin>>x>>N;
	while(N--){
		int64_t x_=x,p=1,a;
		std::cin>>a;
		while(a){if(a&1)p*=x_;p%=m;x_*=x_;x_%=m;a/=2;}
		sum+=p;
	}
	std::cout<<(sum%m);
}