l=lambda:map(int,raw_input().split())
x,n=l()
m=1000003
print sum(pow(x,i,m)for i in l())%m