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

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

  answer = 0
  for a in A:
    answer += x ** a

  print(answer % 1000003)

main()