unittest
{
	assert( [ "10" ].parse.expand.solve == 5 );
	assert( [ "1111111111111111111" ].parse.expand.solve == 162261460 );
	
	assert( [ "111" ].parse.expand.solve == 27 );		// 追加ケース
	assert( [ "101" ].parse.expand.solve == 15 );		// 追加ケース
	assert( [ "011" ].parse.expand.solve == 9 );		// 追加ケース
	assert( [ "010" ].parse.expand.solve == 5 );		// 追加ケース
}



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未満が確定している場合のパターン数を計算
		// i桁目で初めてl未満が確定する場合の(a[i],b[i])は (0,0) の1パターン（ただし、l[i]==0 のときは上に含まれるので0パターン）
		// i-1桁目までで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 ) ) + ( dp[ i ][ 1 ] * 3 ) % MOD ) % MOD;
	}
	return ( dp[ $ - 1 ][ 0 ] + dp[ $ - 1 ][ 1 ] ) % MOD;
}
