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