# your code goes here
x,N=(int(i) for i in input (). split ())
a=[int(i) for i in input (). split ()]
k=0
for i in range (N):
  #  print (
    k+=x**a[i]
    k%=10000003
#    print (k)
print (k)