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



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;

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

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto l = input.front.map!( ( a ) => a == '1' ).array;
	
	// 桁DP
	// dp[ i桁目 ][ l未満フラグ ] = パターン数
	const M = 10L ^^ 9 + 7;
	auto dp = new ModWorld!M[][]( 1 + l.length, 2 );
	dp[ 0 ][ 0 ] = 1;
	foreach( i, c; l )
	{
		// a+b==l --> a+b==l の場合
		if( c ) dp[ i + 1 ][ 0 ] = dp[ i ][ 0 ] * 2;		// a[i]=1,b[i]=0 もしくは a[i]=0,b[i]=1
		else    dp[ i + 1 ][ 0 ] = dp[ i ][ 0 ];			// a[i]=0,b[i]=0
		
		// a+b==l --> a+b<l の場合
		if( c ) dp[ i + 1 ][ 1 ] = dp[ i ][ 0 ];			// a[i]=0,b[i]=0
		
		// a+b<l --> a+b<l の場合
		dp[ i + 1 ][ 1 ] += dp[ i ][ 1 ] * 3;				// a[i]=1,b[i]=0 もしくは a[i]=0,b[i]=1 もしくは a[i]=0,b[i]=0
	}
	return dp[ $ - 1 ].sum;
}

// モジュラ整数型（n mod M）
struct ModWorld( long M )
{
	long n;
	
	void opUnary( string OP )() if( OP == "++" ){ this.n = ( this.n + 1 ) % M; }
	void opUnary( string OP )() if( OP == "--" ){ this.n = ( this.n + M - 1 ) % M; }
	void opOpAssign( string OP )( ModWorld r ) if( OP == "+"  ){ this.n = ( this.n + r.n ) % M; }
	void opOpAssign( string OP )( ModWorld r ) if( OP == "-"  ){ this.n = ( this.n + M - r.n ) % M; }
	void opOpAssign( string OP )( ModWorld r ) if( OP == "*"  ){ this.n = ( this.n * r.n ) % M; }
	void opOpAssign( string OP )( ModWorld r ) if( OP == "/"  ){ this *= r ^^ ModWorld( M - 2 ); }
	void opOpAssign( string OP )( ModWorld r ) if( OP == "^^" )
	{
		auto a = this.n;
		this.n = 1L;
		for( auto i = r.n; 0 < i; i >>= 1 )
		{
			if( i & 1 ) this.n = ( this.n * a ) % M;
			a = ( a * a ) % M;
		}
	}
	auto opBinary( string OP )( ModWorld r ){ auto l = this; l.opOpAssign!OP( r ); return l; }
	
	void opAssign( long r ){ this.n = r; }
	void opOpAssign( string OP )( long r ){ this.opOpAssign!OP( ModWorld( r ) ); }
	auto opBinary( string OP )( long r ){ return this.opBinary!OP( ModWorld( r ) ); }
	auto opBinaryRight( string OP )( long l ){ return ModWorld( l ).opBinary!OP( this ); }
	auto opEquals( long r ){ return this.n == r; }
	
	auto toString(){ return this.n.to!string; }
}
