E. 完美切割

时间限制： 每测试 $2$ 秒
内存限制： 每测试 $256$ 兆字节

你将得到一个由字符 0、1 和/或 ? 组成的字符串 $s$。

我们称一个二进制字符串（仅由 0 和/或 1 组成）是完美的，如果你能将字符串切成两个非空部分：一个前缀 $a$ 和一个后缀 $b$，使得对于每个 $i$（从 $1$ 到 $\min(|a|, |b|)$），都有 $a_i \geq b_i$。

你的任务是计算将所有问号独立地替换为 0 或 1，使得字符串变为完美的方法数量。如果在至少一个位置上两种方式生成的字符不同，则认为两种方式不同。由于答案可能很大，请输出对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $t$ $(1 \leq t \leq 10^4)$ — 测试用例的数量。

每个测试用例只有一行，包含一个字符串 $s$ $(2 \leq |s| \leq 2 \cdot 10^5)$，由字符 0、1 和/或 ? 组成。

额外约束：所有测试用例的字符串长度之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 — 将所有问号独立替换为 0 或 1，使得字符串变为完美的方法数量，对 $998244353$ 取模。

样例

输入

5
0?1
011
????
110?0
0?1?

输出

1
0
15
2
3

样例解释

第一个测试用例：字符串 001 可以拆分为长度为 $1$ 的前缀和长度为 $2$ 的后缀，满足完美条件。替换方式：0?1 → 001，只有这一种。

第二个测试用例：字符串 011 无论如何切割，都无法满足完美条件，答案为 $0$。

第三个测试用例：字符串 ???? 共有 $15$ 种替换方式可以使其变为完美字符串。

第四个测试用例：可以得到的完美字符串有：

• 字符串 11010，可以拆分为长度为 $2$ 的前缀和长度为 $3$ 的后缀；
• 字符串 11000，可以拆分为长度为 $4$ 的前缀和长度为 $1$ 的后缀。

共 $2$ 种方式。

第五个测试用例：字符串 0?1? 共有 $3$ 种替换方式可以使其变为完美字符串。