x,n=map(int,input().split())
l=list(map(int,input().split()))
t=0
for a in l:
	t+=x**a
	if t>1000003: t%=1000003
print(t)