s,d=0,1000003;x=gets;gets.split.map{|e|s+=x.to_i**(e.to_i%~-d)};p s%d