gets;$/=' ';p$<.sum{$_.to_i.pow _1.to_i,M=1000003}