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
1,1,1,1, 1,1,1,1, 0,0,0,0,
1,1,1,1, 0,0,1,1, 0,0,0,0,
1,1,1,1, 0,0,0,0, 1,1,0,0,
1,1,1,1, 0,0,0,0, 1,1,1,1,

0,0,1,1, 1,1,0,0, 0,0,0,0,
0,0,1,1, 1,1,1,0, 0,0,0,0,
0,0,0,1, 0,1,1,1, 0,0,0,0,
0,0,0,1, 0,0,1,1, 0,0,0,0,

1,0,0,0, 0,0,0,0, 1,1,0,0,
1,0,0,0, 0,0,0,0, 1,1,1,0,
1,1,0,0, 0,0,0,0, 0,1,1,1,
1,1,0,0, 0,0,0,0, 0,0,1,1
while$=--;print$Z[3]