CF2256B Domino Tiles

Nygglatho 从市场上带回一个旧瓷砖盒子，上面的图案已经开始褪色。还没等她收好，Chtholly 和小妖精们已经把瓷砖铺在餐桌上并把它们变成了一个谜题。 现在有一排 $n$ 块瓷砖。每块瓷砖应当被标记为 $0$ 或 $1$，但有些标记已经褪色。 当前瓷砖排用一个长度为 $n$ 的字符串 $s$ 表示。$s$ 的每个字符可以是 $0$、$1$ 或 $?$。Chtholly 需要将每个 $?$ 替换为 $0$ 或 $1$。 所有 $?$ 都被替换后，对于每一个 $1 \le i < n$，相邻的两块瓷砖 $s_i$ 和 $s_{i+1}$ 组成一个权值为 $s_i + s_{i+1}$ 的多米诺骨牌（注意这里的加法是数值加法）。相邻的两个多米诺只会共享一块瓷砖。当完成后的所有相邻多米诺骨牌权值都两两不同，则这一排瓷砖是合法的。 请你计算有多少种不同的方案替换 $?$，使得填充后的瓷砖排是合法的。请将答案对 $998\,244\,353$ 取模后输出。 如果两种替换方案得到的字符串不同，则认为它们是不同的方案。

每个测试包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示瓷砖的数量。 第二行包含一个长度为 $n$ 的字符串 $s$，其中 $s_i$ 可以是 $0$、$1$ 或 $?$。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试数据，输出一个整数，表示合法替换方案的数量，对 $998\,244\,353$ 取模。

在第一个测试用例中，只有一个多米诺骨牌，所以每种填充方案都是合法的。可以得到的合法字符串有 $00$、$01$、$10$、$11$。 在第二个测试用例中，合法填充后的字符串为 $00110$ 和 $01100$。 在第三个测试用例中，不存在合法的填充字符串。 在第四个测试用例中，唯一合法的填充字符串为 $00110011$。 由 ChatGPT 5 翻译