unittest
{
	assert( [ "10" ].parse.expand.solve == 5 );
	assert( [ "1111111111111111111" ].parse.expand.solve == 162261460 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto l = input.front;
	return tuple( l );
}

auto solve( string l )
{
	const MOD = 10L ^^ 9 + 7;
	
	auto dp = new Tuple!( long, long )[ 1 + l.length ];
	dp[ 0 ][ 0 ] = 1;
	dp[ 0 ][ 1 ] = 0;
	foreach( i, b; l )
	{
		// i桁目までlと同じにする場合のパターン数を計算
		// (a[i],b[i])は l[i]==1 だったら (1,0)or(0,1) の2パターン、 l[i]==0 だったら (0,0) の1パターン
		dp[ 1 + i ][ 0 ] = ( dp[ i ][ 0 ] * ( b == '1' ? 2 : 1 ) % MOD );
		
		// i桁目まででl未満にする場合のパターン数を計算
		// (a[i],b[i])は (1,0)or(0,1)or(0,0) の3パターン
		dp[ 1 + i ][ 1 ] = ( ( dp[ i ][ 0 ] * ( b == '1' ? 1 : 0 ) % MOD ) + ( dp[ i ][ 1 ] * 3 % MOD ) % MOD );
	}
	return dp[ $ - 1 ][ 0 ] + dp[ $ - 1 ][ 1 ];
}
