d=10**6+3
x,n,*a=$<.read.split.map{|e|e.to_i%d}
s=0
a.map{|e|t=1;e.times{t=(t*x)%d};s+=t}
p s%=d