Problem Statement

For a string $X$ consisting only of '0' and '1', define $f(X)$ as the number of occurrences of $\mathsf {010}$ contained in $X$ as a subsequence (not necessarily contiguous).
Subsequences are distinguished by the positions they are taken from.

You are given a string $S$ consisting only of '0', '1', and '?'.

Replace every '?' in $S$ with '0' or '1' to create a string $S'$.
There are $2^c$ such strings $S'$, where $c$ is the number of '?' in $S$. Find the sum of $f(S')$ over all of them.

Since the answer can be very large, output it modulo $998244353$.

Input

$S$

• $S$ is a string consisting only of '0', '1', and '?'
• $1 \leq |S| \leq 2 \times 10^5$

Output

Output the sum of $f(S')$ over all possible $S'$, modulo $998244353$.

Sample

01?0

4

0

0

??????????

15360