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

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