sub mul{
	my@C;
	for$y(0..9){
		for$x(0..9){
			($C[$y*10+$x]+=$Z[$y*10+$_]*$_[$_*10+$x])%=1e9+7for 0..9
		}
	}
	@C
}

@@=(
	1,1,1,1,1,1,1,1,0,0,
	0,1,1,1,0,0,0,1,0,1,
	0,1,1,1,1,1,0,0,0,1,
	0,1,1,1,1,1,1,0,1,1,
	0,0,1,1,1,1,0,0,0,1,
	0,0,1,1,1,1,1,0,0,1,
	0,0,0,1,0,1,1,1,0,1,
	0,0,0,1,0,0,0,1,0,0,
	0,1,0,0,0,0,1,0,1,1,
	0,0,0,0,0,0,0,0,0,1
);
$Z[11*$_]=1for 0..9;

$.+=<>;
(@Z=mul@Z),$.>>$=&1and@Z=mul@@while$=--;
print$Z[9]