x,a = map(int, raw_input().split())
al = map(int,raw_input().split())
sum = 0
for i in al:
  sum += x**i
print(sum%1000003)