def main():
  x, N = list(map(
    int, input().split()
  ))

  A = list(map(
    int, input().split()
  ))

  answer = 0
  for a in A:
    answer += (x ** a) % 1000003

  print(answer)

main()