[AGC022E] Median Replace
题意翻译
有个长度为 $N$($N$ 为奇数)的 $\texttt{01}$ 串 $s$,其中有若干位置是 $\texttt{?}$。
一次操作可将 $3$ 个连续的字符替换成这三个数的中位数。
求有多少将 $\texttt ?$ 替换成 $\texttt0$ 或 $\texttt1$ 的方案使得进行 $\frac{N-1}{2}$ 次操作后的字符串可以是 $\texttt1$。
题目描述
[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 $ で割った余りをタイチは知りたいです。
输入输出格式
输入格式
入力は標準入力から以下の形式で与えられる。
> $ S $
输出格式
`?` を置き換える方法であって、美しい文字列が得られるものの個数を $ 10^{9}\ +\ 7 $ で割った余りを出力せよ。
输入输出样例
输入样例 #1
1??00
输出样例 #1
2
输入样例 #2
?
输出样例 #2
1
输入样例 #3
?0101???10???00?1???????????????0????????????1????0
输出样例 #3
402589311
说明
### 制約
- $ 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 $ で割った余りを出力することを忘れずに。