use bigint;<>=~/ /;$/=$";$r+=(0+$`)->bmodpow($_,1e6+3)for<>;print$r%1000003