import math

def powmod(x, a, m):
  if a == 0:
    return 1
  elif a % 2 == 1:
    return (x * powmod(x, a - 1, m)) % m
  else:
    return pow(powmod(x, a // 2, m), 2) % m
    
x, n = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

ans = 0
for i in range(n):
  ans += powmod(x, a[i], 1000003)

print(ans)