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

x,n=map(int,input().split())
a=list(map(int,input().split()))
m=1000003
print(sum([p(x,i,m) for i in a]))