sub f{my@r;$y=$_*12,map{//;($r[$y+$']+=$Z[$y+$_]*$_[$_*12+$'])%=1e9+7for@@}@@for@@;@r}$Z[13*$_]=1for@@=0..11;$N=<>;(@Z=f@Z),$N+1>>$=&1and@Z=f map{vec"ÿðóð<Àè€
p>À",$_,1}0..143while$=--;print$Z[3]