gets
$/=" "
p$<.map{|a|$_.to_i.**a.to_i%1000002}.sum%1000003