$"='';
$b=($a=1e9)+7;
@N=<>=~/./g;
$K=@N;
$t+="@N[0..$K-1>>1,reverse 0..($K>>1)-1]"le"@N";
--$N[0];
exec"dc -e'
A $K 1-2/$a|A $K 2/$a|+$a+2-@N[0..$K-1>>1] $a%$t++$a%p
A $K 1-2/$b|A $K 2/$b|+$b+2-@N[0..$K-1>>1] $b%$t++$b%p
'"