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