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