a,_=map(int,input().split());b=0
for x in list(map(int,input().split())):b+=pow(a,x)
print(b%(10**6+3))