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