d=1000003
x,n,*a=$<.read.split.map{|e|e.to_i%d}
w=->n{n<1?1:(_=w[x*x,n/2]%d;n&1<1)?_:_*x}
s=0;a.map{|e|s+=w[e]};p s%d