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