m = 100000000

x, n = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

l = [1 for x in range(m + 1)]


for i in range(m):
  tmp = l[i] * x
  
  if tmp > 1000002:
    l[i + 1] = tmp % 1000003
  else:
    l[i + 1] = tmp

ans = 0

for i in a:
  ans += l[i]

print(ans)