CF2256B.Domino Tiles

Nygglatho returns from the market with an old box of tiles whose painted marks have begun to fade. Before she can put it away, Chtholly and the young fairies have already spread the tiles across the dining table and turned them into a puzzle.

There is a row of $n$ tiles. Each tile should be marked with either $\mathtt 0$ or $\mathtt 1$. However, some of the marks have faded away.

The current row is represented by a string $s$ of length $n$. Each character of $s$ is $\mathtt{0}$, $\mathtt{1}$, or $\mathtt{?}$. Chtholly must replace every $\mathtt{?}$ with either $\mathtt{0}$ or $\mathtt{1}$.

After replacement, for every $1 \le i \lt n$, the two neighboring tiles $s_i$ and $s_{i+1}$ form a domino of weight $(s_i + s_{i+1})$. Note that two consecutive dominoes share exactly one tile. The completed row is valid if every two consecutive dominoes have different weights.

Determine the number of different$^{\text{∗}}$ ways to replace all $\mathtt{?}$ characters so that the completed row is valid. Output the answer modulo $998\,244\,353$.

$^{\text{∗}}$Two ways of replacement are considered different if the resulting strings are different.

尼格拉索从市场归来，带回了一个装有旧瓷砖的盒子，瓷砖上的彩绘标记已经开始褪色。她还没来得及把盒子收好，楚托莉和一群小精灵就已经把瓷砖铺满了餐桌，并将其变成了一道谜题。

有一排 $n$ 块瓷砖。每块瓷砖上应标有 $\mathtt{0}$ 或 $\mathtt{1}$。然而，其中一些标记已经褪色。

当前这一排用一个长度为 $n$ 的字符串 $s$ 表示。$s$ 的每个字符为 $\mathtt{0}$、$\mathtt{1}$ 或 $\mathtt{?}$。楚托莉必须将每个 $\mathtt{?}$ 替换为 $\mathtt{0}$ 或 $\mathtt{1}$。

替换完成后，对每个 $1 \le i \lt n$，相邻的两块瓷砖 $s_i$ 与 $s_{i+1}$ 构成一个权值为 $(s_i + s_{i+1})$ 的多米诺骨牌。注意：两个连续的多米诺骨牌恰好共享一块瓷砖。若完成后的整排中，任意两个连续的多米诺骨牌权值均不相同，则称该排是有效的。

求出将所有 $\mathtt{?}$ 替换为 $\mathtt{0}$ 或 $\mathtt{1}$ 后，使得整排有效的不同方式数目（模 $998\,244\,353$）。

$^{\text{∗}}$ 若两种替换方式所得字符串不同，则认为它们是不同的方式。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of tiles.

The second line contains the string $s$ of length $n$, where $s_i= \mathtt{0}$, $\mathtt{1}$, or $\mathtt{?}$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 表示瓷砖的数量。

第二行包含一个长度为 $n$ 的字符串 $s$，其中每个字符 $s_i$ 为 $\mathtt{0}$、$\mathtt{1}$ 或 $\mathtt{?}$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output one integer — the number of valid ways to replace all $\mathtt{?}$ characters, modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——将所有 $\mathtt{?}$ 字符替换为有效字符的方案数，对 $998\,244\,353$ 取模。

In the first test case, there is only one domino, so every completion is valid. The valid completed strings are $\mathtt{00}$, $\mathtt{01}$, $\mathtt{10}$, and $\mathtt{11}$.

In the second test case, the valid completed strings are $\mathtt{00110}$ and $\mathtt{01100}$.

In the third test case, there are no valid completed strings.

In the fourth test case, the only valid completed string is $\mathtt{00110011}$.

在第一个测试用例中，只有一个多米诺骨牌，因此所有补全方案均有效。有效的补全字符串为 $\mathtt{00}$、$\mathtt{01}$、$\mathtt{10}$ 和 $\mathtt{11}$。

在第二个测试用例中，有效的补全字符串为 $\mathtt{00110}$ 和 $\mathtt{01100}$。

在第三个测试用例中，不存在有效的补全字符串。

在第四个测试用例中，唯一有效的补全字符串为 $\mathtt{00110011}$。