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