题目描述

有一排共 $n$ 块瓷砖。每块瓷砖上应当标记有 0 或 1。然而，有些标记已经褪色看不清了。

目前这一排瓷砖用一个长度为 $n$ 的字符串 $s$ 来表示。$s$ 中的每个字符为 0、1 或 ?。你必须将所有的 ? 替换为 0 或 1。

在替换完成后，对于每一个 $1 \le i < n$，相邻的两块瓷砖 $s_i$ 和 $s_{i+1}$ 会构成一个“多米诺骨牌”，其“重量”定义为 $(s_i + s_{i+1})$。注意，相邻的两个多米诺骨牌会恰好共用一块瓷砖。如果任意两个相邻的多米诺骨牌都具有不同的重量，我们就称这排完整的瓷砖是合法的。

请你计算出，有多少种不同的方式将所有的 ? 进行替换，使得最终这排瓷砖是合法的。将答案对 $998244353$ 取模后输出。

如果两种替换方式得到的最终字符串不同，则认为这两种方式是不同的。

输入格式

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

对于每个测试用例：

• 第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$）—— 瓷砖的数量。
• 第二行包含一个长度为 $n$ 的字符串 $s$，其中 $s_i \in \{\text{'0'}, \text{'1'}, \text{'?'}\}$。

输出格式

对于每个测试用例，输出一行一个整数，表示合法的替换方式数量对 $998244353$ 取模后的结果。

样例输入 1

4
2
??
5
0?1??
5
0?0??
8
00110011

样例输出 1

4
2
0
1

说明

样例解释

• 在第一个测试用例中，只有一个多米诺骨牌，所以任何填法都是合法的。合法的完整字符串为 00、01、10 和 11。
• 在第二个测试用例中，合法的完整字符串有 00110 和 01100。
• 在第三个测试用例中，不存在任何合法的完整字符串。
• 在第四个测试用例中，唯一的合法完整字符串就是它本身 00110011。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于每个测试用例，保证 $2 \le n \le 2 \times 10^5$。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。
• 保证字符串 $s$ 仅由 0、1、? 组成。