def p(x,n):
  v=1
  while n:
    if n&1:
      v*=x
      n-=1
    elif n:
      x**=2
      n//=2
  return v

x,n=map(int,input().split())
a=list(map(int,input().split()))
m=1000003
v=0
while a:
  v+=p(x,a.pop()%m)
print(v%m)