sub f{my@r;$y=$_*10,map{//;($r[$y+$']+=$Z[$y+$_]*$_[$_*10+$'])%=1e9+7for@@}@@for@@;@r}$Z[11*$_]=1for@@=0..9;$N=<>;(@Z=f@Z),$N+1>>$=&1and@Z=f map{vec'ÿ8ê£ß<ò‰."B',$_,1}0..99while$=--;print$Z[9]