sub f{my@r;$y=$_*28,map{//;($r[$y+$']+=$Z[$y+$_]*$_[$_*28+$'])%=1e9+7for@@}@@for@@;@r}$Z[29*$_]=1for@@=0..27;$N=<>;(@Z=f@Z),$N+1>>$=&1and@Z=f map{vec'вD)@┤В(D+┤@А$@Р@В(АвD@@д Ад @РвD H',$_,1}0..783while$=--;print$Z[1]