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