import itertools

x, a = map(int, input().split())
inpls = list(map(int,input().split()))

sm = 0
for i in inpls:
    sm += pow(x,i,1000003)

print(sm%1000003)