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