d=1000003;x=gets;$/=' ';p $<.map{|e|x.to_i**(e.to_i%~-d)}.sum%d