Balanced 01-String

题号：NC311835
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有一个长度为 $n$ 的字符串 $s$ ，只包含字符 $\texttt{'0'}$ 、 $\texttt{'1'}$ 和 $\texttt{'?'}$ 。

$\hspace{15pt}$ 他定义一个 $01$ 字符串是平衡的，当且仅当字符串中所有相邻两个字符相同的对数（即满足 $s_i = s_{i+1}$ 的 $i$ 的数量）是偶数。

$\hspace{15pt}$ （特别的，长度为 $1$ 的 $01$ 串必然是平衡的，因为此时相邻相同对数为 $0$ ， $0$ 也是偶数。）

$\hspace{15pt}$ 小苯可以将每个 $\texttt{'?'}$ 替换为 $\texttt{'0'}$ 或 $\texttt{'1'}$ 。你的任务是求出，在所有可能的替换结果中，有多少个 $01$ 字符串是平衡的？（结果对 $998244353$ 取模。）

第一行一个整数 ，表示测试数据组数。
接下来  行，每行一个字符串 ，只包含 、、。

保证所有测试数据的字符串长度  之和不超过 。

对于每组数据，输出一个整数表示满足条件的  字符串数量对  取模的结果。

示例1

复制

2
0?1
????

复制

0
8

第一组数据：，两种替换：
：相邻相同对数为 （），奇数，不平衡。
：相邻相同对数为 （），奇数，不平衡。
输出 。