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

@T=(
	[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]
);
for$y(0..9){
	for$x(0..9){
		$Z[$y][$x]=$x==$y
	}
}

$N=<>;
for(reverse 0..59){
	@Z=@{;mul[@Z],[@Z]};
	if($N+1>>$_&1){
		@Z=@{;mul[@Z],[@T]}
	}
}
print$Z[0][9]