E - Median Replace 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 1600 点

問題文

タイチは、0 と 1 からなる奇数長 N の文字列 X は次の条件を満たすとき 美しい と考えています。条件：次の操作を \frac{N-1}{2} 回行って、最終的な文字列の唯一の文字を 1 にすることができる。

  • X の 連続する 3 つのビットを選び、それらの中央値でそれらを置き換える。例えば、00110 の中央の 3 ビットに操作を適用すると、この文字列は 010 となる。

タイチは 0、1、? からなる文字列を持っています。この文字列の ? をそれぞれ 1 か 0 に置き換える方法であって、美しい文字列が得られるものの個数を 10^{9} + 7 で割った余りをタイチは知りたいです。

制約

  • 1 \leq |S| \leq 300000
  • |S| は奇数である。
  • S のすべての文字は 0、1、? のいずれかである。

入力

入力は標準入力から以下の形式で与えられる。

S

出力

? を置き換える方法であって、美しい文字列が得られるものの個数を 10^{9} + 7 で割った余りを出力せよ。

入力例 1

1??00

出力例 1

2

? を 0 か 1 で置き換える方法は以下の 4 通りあります。

  • 11100 : この文字列は美しいです。なぜなら、まず最後の 3 ビットに操作を適用して 110 とし、次に文字列全体に操作を適用すると 1 となるからです。

  • 11000 : この文字列は美しいです。なぜなら、まず最後の 3 ビットに操作を適用して 110 とし、次に文字列全体に操作を適用すると 1 となるからです。

  • 10100 : この文字列は美しくありません。なぜなら、最終的に文字列が 1 となるような操作手順が存在しないからです。

  • 10000 : この文字列は美しくありません。なぜなら、最終的に文字列が 1 となるような操作手順が存在しないからです。

よって、美しい文字列を得る方法は 2 通りです。

入力例 2

?

出力例 2

1

この場合、1 が唯一の美しい文字列です。

入力例 3

?0101???10???00?1???????????????0????????????1????0

出力例 3

402589311

答えを 10^{9} + 7 で割った余りを出力することを忘れずに。

Score : 1600 points

Problem Statement

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 :

  • Choose three consecutive bits of X 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 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.

Constraints

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

Input

Input is given from Standard Input in the following format:

S

Output

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

Sample Input 1

1??00

Sample Output 1

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.

Sample Input 2

?

Sample Output 2

1

In this case, 1 is the only beautiful string.

Sample Input 3

?0101???10???00?1???????????????0????????????1????0

Sample Output 3

402589311

Remember to output your answer modulo 10^{9} + 7.