配点 : $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??00

2

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

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

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

?

1

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

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

402589311

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