CF2141E.Perfect Cut

给定一个由字符 $0$、$1$ 和（或）$?$ 组成的字符串 $s$。

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

你的任务是计算将所有问号独立替换为 $0$ 或 $1$，使得最终串为“完美串”的方案数。两种方案被认为不同，当且仅当存在至少一个位置的字符不同。由于答案可能很大，输出其对 $998244353$ 取模的结果。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例数量。

每个测试用例仅一行，包含字符串 $s$（$2 \le |s| \le 2 \cdot 10^5$），由字符 $0$、$1$ 和 $?$ 组成。

输入的额外限制：所有测试用例中字符串 $s$ 的总长度不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示将所有问号独立替换为 $0$ 或 $1$，使得最终串为“完美串”的方案数，对 $998244353$ 取模。

在第一个测试用例中，串 001 可以被分割成长度为 $1$ 的前缀和长度为 $2$ 的后缀。

在第四个测试用例中，以下字符串可以被得到：

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

由 ChatGPT 5 翻译