给定一个由字符组成的字符串 $$$s$$$ 0, 1,和/或 ?.
让我们调用一个二进制文件(由 0 和/或 1) 字符串 完美 如果你可以将字符串切成两个非空部分:前缀 $$$a$$$ 和后缀 $$$b$$$,这样 $$$a_i \ge b_i$$$ 对于每个 $$$i$$$ 从 $$$1$$$ 到 $$$\min(|a|, |b|)$$$。
您的任务是计算将所有问号(独立地)替换为 0 和 1 的方法数量,以便生成的字符串是完美的 mod。如果两种方式中至少存在一个位置具有不同的字符,则认为这两种方式是不同的。由于答案可能很大,因此打印它对 $$$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$$$ 为模。
示例
输入复制
50?1011????110?00?1?
输出复制
1 0 15 2 3
注意
在第一个测试用例中,字符串 001 可以分为长度为 $$$1$$$ 的前缀和长度为 $$$2$$$ 的后缀。
在第四个测试用例中,可以获得以下字符串:
- 字符串 11010,可以拆分为长度为 $$$2$$$ 的前缀和长度为 $$$3$$$ 的后缀;
- 字符串 11000,可以分为长度为 $$$4$$$ 的前缀和长度为 $$$1$$$ 的后缀。