問題文

'0' と'1' のみから成る文字列 $X$ に対し、 $f(X)$ を $X$ に部分列（連続でなくてもよい） として含まれる $\mathsf {010}$ の個数と定めます。
ただし部分列は取り出した位置で区別します。

'0', '1', '?' のみから成る文字列 $S$ が与えられます。

$S$ の全ての '?' を '0' または '1' に置き換え、文字列 $S'$ を作ります。
このような $S'$ は $S$ に含まれる'?' の個数を $c$ として $2^c$ 通りありますが、それらすべてに対する $f(S')$ の総和を求めてください。

答えは非常に大きくなることがあるので、$998244353$ で割った余りを出力してください。

入力

$S$

• $S$ は '0', '1', '?' のみから成る文字列
• $1 \leq |S| \leq 2 \times 10^5$

出力

考え得る $S'$ 全てに対する $f(S')$ の総和を $998244353$ で割った余りを出力してください。

サンプル

01?0

4

0

0

??????????

15360