x,N=map(int,input().split());b=0;mod=1000003
for i in list(map(int,input().split())):
	b=(b+pow(x,i,mod))%mod
print(b)