x,n=map(int,input().split())
a=list(map(int,input().split()))
M=1000003
g=0
for v in a:
	g+=pow(x,v,M)
	g%=M
print(g)