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