U736580 I - 鬼人正邪Ⅱ

种族：天邪鬼。 能力：能让任何事物翻转过来的程度的能力。 企图下克上的天邪鬼。 天邪鬼不属于鬼，只是一种性格扭曲的妖怪。 她一天到晚脑子里都想着和其他人相反的事情。 别人一反感她就高兴，看到别人一高兴她就开始心生厌恶。 她绝对不服从命令。就算自己赚了，也绝不会把别人应得的给对方。 这样的家伙当然会被人类、妖怪双方厌恶，但别人越是讨厌她，她自然就越高兴。 而她的野心，就是把幻想乡整个翻转过来。 毁掉如今这个由强者稳定支配的幻想乡，把这里变成一个由弱者说了算的世界。 只是，她没有能够实现这个梦想的力量。 因此，她盯上了小人手上的秘宝「万宝槌」。

现在给鬼人正邪一个长度为 $n$ 的 `01` 串 $a$。 她可以进行任意多次操作（包括零次操作）： 选择两个位置 $l,r$（$1\le l

第一行输入一个整数 $T$，表示测试数据组数。 对于每组测试数据： 第一行输入一个整数 $n$，表示 `01` 串的长度。 第二行输入一个长度为 $n$ 的 `01` 串 $a$。

对于每组测试数据，输出一行一个整数，表示能够得到的不同 `01` 串数量。 答案对 $998244353$ 取模。

#### **样例解释** 对于第一组数据，初始字符串为 ```text 0110 ``` 能够得到的不同字符串为 ```text 0110 0000 0100 0010 ``` 共 $4$ 种。 对于第二组数据，初始字符串为 ```text 0101 ``` 能够得到的不同字符串为 ```text 0101 0001 0111 ``` 共 $3$ 种。 #### **数据范围** 对于所有测试数据，保证： $$ 1\le T\le 10^4, $$ $$ 1\le n\le 2\times 10^5, $$ 且所有测试数据的 $n$ 之和不超过 $$ 2\times 10^5. $$ 字符串中的每个字符均为 `0` 或 `1`。 详细的子任务限制如下： | 子任务 | 分值 | 特殊性质 | | :-: | :----: | :----------------------- | | 1 | $20$ 分 | $n\le 4$ | | 2 | $80$ 分 | 无特殊限制 |