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