<>=~/\s/,$m=1e6+3,$a=1/$`;push@b,$a=($a*$`)%$m for 0..$m;$r+=$b[$_%($m-1)]for<>=~/\S+/g;print$r%$m