lst=[1]
def calc(x,a):
  d=bin(a)[2:]
  ans=1
  for i in xrange(len(d)):
    if d[i]=="1":
      ans*=lst[len(d)-i]
  return ans

x,N=map(int,raw_input().split())
lst.append(x)
for i in xrange(2,33):
  lst.append(lst[i-1]**2%1000003)
a=map(int,raw_input().split())
ans=0
for i in xrange(N):
  ans+=calc(x,a[i])
  ans=ans%1000003
print ans