<>;
for$s(<>){
	$%=1e9;
	for$i(0..length($s)-12){
		$g=(good^substr$s,$i,4)=~y/\x00//c;
		for$j($i+4..length($s)-8){
			$%-=$-=$%-$g-(problem^substr$s,$j,7)=~y/\x00//c;
		}
	}
	print$%,$/
}