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