Score : 1600 points
Taichi thinks a binary string X of odd length N is beautiful if it is possible to apply the following operation \frac{N-1}{2} times so that the only character of the resulting string is 1
:
00110
into 010
by applying the operation to the middle three bits.Taichi has a string S consisting of characters 0
, 1
and ?
. Taichi wants to know the number of ways to replace the question marks with 1
or 0
so that the resulting string is beautiful, modulo 10^{9} + 7.
0
, 1
or ?
.Input is given from Standard Input in the following format:
S
Print the number of ways to replace the question marks so that the resulting string is beautiful, modulo 10^{9} + 7.
1??00
2
There are 4 ways to replace the question marks with 0
or 1
:
11100
: This string is beautiful because we can first perform the operation on the last 3 bits to get 110
and then on the only 3 bits to get 1
.
11000
: This string is beautiful because we can first perform the operation on the last 3 bits to get 110
and then on the only 3 bits to get 1
.
10100
: This string is not beautiful because there is no sequence of operations such that the final string is 1
.
10000
: This string is not beautiful because there is no sequence of operations such that the final string is 1
.
Thus, there are 2 ways to form a beautiful string.
?
1
In this case, 1
is the only beautiful string.
?0101???10???00?1???????????????0????????????1????0
402589311
Remember to output your answer modulo 10^{9} + 7.