x,N=map(int,input().split())
A=list(map(int,input().split()))
m=1000003
s=0
for v in A: s+=pow(x,v,m)
print(s%m)