atcoder#AGC022E. [AGC022E] Median Replace

[AGC022E] Median Replace

Score : 16001600 points

Problem Statement

Taichi thinks a binary string XX of odd length NN is beautiful if it is possible to apply the following operation N12\frac{N-1}{2} times so that the only character of the resulting string is 1 :

  • Choose three consecutive bits of XX and replace them by their median. For example, we can turn 00110 into 010 by applying the operation to the middle three bits.

Taichi has a string SS 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 109+710^{9} + 7.

Constraints

  • 1S3000001 \leq |S| \leq 300000
  • S|S| is odd.
  • All characters of SS are either 0, 1 or ?.

Input

Input is given from Standard Input in the following format:

SS

Output

Print the number of ways to replace the question marks so that the resulting string is beautiful, modulo 109+710^{9} + 7.

1??00
2

There are 44 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 33 bits to get 110 and then on the only 33 bits to get 1.
  • 11000 : This string is beautiful because we can first perform the operation on the last 33 bits to get 110 and then on the only 33 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 22 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 109+710^{9} + 7.