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

s = 0

for i in range(n):
  s += x ** a[i]

print(s % 1000003)