AT_agc022_e [AGC022E] Median Replace

[problemUrl]: https://atcoder.jp/contests/agc022/tasks/agc022_e タイチは、`0` と `1` からなる奇数長 $ N $ の文字列 $ X $ は次の条件を満たすとき **美しい** と考えています。条件：次の操作を $ \frac{N-1}{2} $ 回行って、最終的な文字列の唯一の文字を `1` にすることができる。 - $ X $ の **連続する** $ 3 $ つのビットを選び、それらの中央値でそれらを置き換える。例えば、`00110` の中央の $ 3 $ ビットに操作を適用すると、この文字列は `010` となる。 タイチは `0`、`1`、`?` からなる文字列を持っています。この文字列の `?` をそれぞれ `1` か `0` に置き換える方法であって、美しい文字列が得られるものの個数を $ 10^{9}\ +\ 7 $ で割った余りをタイチは知りたいです。

N/A

N/A

### 制約 - $ 1\ \leq\ |S|\ \leq\ 300000 $ - $ |S| $ は奇数である。 - $ S $ のすべての文字は `0`、`1`、`?` のいずれかである。 ### Sample Explanation 1 `?` を `0` か `1` で置き換える方法は以下の $ 4 $ 通りあります。 - `11100` : この文字列は美しいです。なぜなら、まず最後の $ 3 $ ビットに操作を適用して `110` とし、次に文字列全体に操作を適用すると `1` となるからです。 - `11000` : この文字列は美しいです。なぜなら、まず最後の $ 3 $ ビットに操作を適用して `110` とし、次に文字列全体に操作を適用すると `1` となるからです。 - `10100` : この文字列は美しくありません。なぜなら、最終的に文字列が `1` となるような操作手順が存在しないからです。 - `10000` : この文字列は美しくありません。なぜなら、最終的に文字列が `1` となるような操作手順が存在しないからです。 よって、美しい文字列を得る方法は $ 2 $ 通りです。 ### Sample Explanation 2 この場合、`1` が唯一の美しい文字列です。 ### Sample Explanation 3 答えを $ 10^{9}\ +\ 7 $ で割った余りを出力することを忘れずに。