[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 $ で割った余りを出力することを忘れずに。