gets
$/=' '
p$<.map{$_.to_i.**_1.to_i%M=1000002}.sum%-~M