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