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"\xa2\x01\x44\x1b\x00\x00\x00\x02\x00\x04\x29\x00\x40\xb4\x00\x00\x82\x04\x00\x00\x02\x00\x00\x28\x00\x00\x00\x01\x02\x00\x44\x2b\x1a\x00\xb4\x40\x00\x80\x24\x18\x40\x90\x40\x00\x82\x04\x01\x00\x02\x14\x00\x28\x80\x00\x00\x01\xa2\x01\x44\x0b\x00\x1a\x00\x00\x40\x00\x00\x40\x18\x00\x00\xa4\x01\x00\x20\x04\x00\x00\x10\x00\x00\x80\x01\x00\x00\xa4\x01\x20\x18\x40\x90\xa2\x01\x44\x0b\x04\x20\x48",$_,1}0..783while$=--;print$Z[1]