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