atcoder#AGC022E. [AGC022E] Median Replace

[AGC022E] Median Replace

配点 : 16001600

問題文

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

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

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

制約

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

入力

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

SS

出力

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

1??00
2

?01 で置き換える方法は以下の 44 通りあります。

  • 11100 : この文字列は美しいです。なぜなら、まず最後の 33 ビットに操作を適用して 110 とし、次に文字列全体に操作を適用すると 1 となるからです。
  • 11000 : この文字列は美しいです。なぜなら、まず最後の 33 ビットに操作を適用して 110 とし、次に文字列全体に操作を適用すると 1 となるからです。
  • 10100 : この文字列は美しくありません。なぜなら、最終的に文字列が 1 となるような操作手順が存在しないからです。
  • 10000 : この文字列は美しくありません。なぜなら、最終的に文字列が 1 となるような操作手順が存在しないからです。

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

?
1

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

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

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