x,_,*a=map(int,open(0).read().split());M=10**6+3;print(sum(pow(x,k,M)for k in a)%M)