CF1762C.Binary Strings are Fun

A binary string$^\dagger$ $b$ of odd length $m$ is good if $b_i$ is the median$^\ddagger$ of $b[1,i]^\S$ for all odd indices $i$ ($1 \leq i \leq m$).

For a binary string $a$ of length $k$, a binary string $b$ of length $2k-1$ is an extension of $a$ if $b_{2i-1}=a_i$ for all $i$ such that $1 \leq i \leq k$. For example, 1001011 and 1101001 are extensions of the string 1001. String $x=$1011011 is not an extension of string $y=$1001 because $x_3 \neq y_2$. Note that there are $2^{k-1}$ different extensions of $a$.

You are given a binary string $s$ of length $n$. Find the sum of the number of good extensions over all prefixes of $s$. In other words, find $\sum_{i=1}^{n} f(s[1,i])$, where $f(x)$ gives number of good extensions of string $x$. Since the answer can be quite large, you only need to find it modulo $998\,244\,353$.

$^\dagger$ A binary string is a string whose elements are either $\mathtt{0}$ or $\mathtt{1}$.

$^\ddagger$ For a binary string $a$ of length $2m-1$, the median of $a$ is the (unique) element that occurs at least $m$ times in $a$.

$^\S$ $a[l,r]$ denotes the string of length $r-l+1$ which is formed by the concatenation of $a_l,a_{l+1},\ldots,a_r$ in that order.

长度为奇数 $m$ 的二进制字符串$^\dagger$ $b$ 称为好字符串，当且仅当对所有奇数下标 $i$（$1 \leq i \leq m$），$b_i$ 是子串 $b[1,i]^\S$ 的中位数$^\ddagger$。

对于长度为 $k$ 的二进制字符串 $a$，长度为 $2k-1$ 的二进制字符串 $b$ 称为 $a$ 的一个扩展，若对所有满足 $1 \leq i \leq k$ 的 $i$，均有 $b_{2i-1} = a_i$。例如，1001011 和 1101001 都是字符串 1001 的扩展；而字符串 $x = $1011011 不是字符串 $y = $1001 的扩展，因为 $x_3 \neq y_2$。注意：$a$ 共有 $2^{k-1}$ 个不同的扩展。

现给定一个长度为 $n$ 的二进制字符串 $s$。请计算 $s$ 的所有前缀对应的“好扩展”的数量之和。换言之，求 $\sum_{i=1}^{n} f(s[1,i])$，其中 $f(x)$ 表示字符串 $x$ 的好扩展的个数。由于答案可能非常大，你只需输出其对 $998\,244\,353$ 取模的结果。

$^\dagger$ 二进制字符串是指其每个字符均为 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。

$^\ddagger$ 对于长度为 $2m-1$ 的二进制字符串 $a$，其中位数是指在 $a$ 中出现次数至少为 $m$ 的（唯一）字符。

$^\S$ $a[l,r]$ 表示由 $a_l, a_{l+1}, \ldots, a_r$ 按顺序拼接而成的、长度为 $r-l+1$ 的字符串。

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 a single integer $n$ ($1 \le n \le 2 \cdot 10^5$), where $n$ is the length of the binary string $s$.

The second line of each test case contains the binary string $s$ of length $n$.

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$（$1 \le n \le 2 \cdot 10^5$），表示二进制字符串 $s$ 的长度。

每个测试用例的第二行包含长度为 $n$ 的二进制字符串 $s$。

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

For each test case, print the answer modulo $998\,244\,353$.

对于每个测试用例，输出答案对 $998\,244\,353$ 取模的结果。

In the first and second test cases, $f(s[1,1])=1$.

In the third test case, the answer is $f(s[1,1])+f(s[1,2])=1+2=3$.

In the fourth test case, the answer is $f(s[1,1])+f(s[1,2])+f(s[1,3])=1+1+1=3$.

$f(\mathtt{11})=2$ because two good extensions are possible: 101 and 111.

$f(\mathtt{01})=1$ because only one good extension is possible: 011.

在第一个和第二个测试用例中，$f(s[1,1])=1$。

在第三个测试用例中，答案为 $f(s[1,1])+f(s[1,2])=1+2=3$。

在第四个测试用例中，答案为 $f(s[1,1])+f(s[1,2])+f(s[1,3])=1+1+1=3$。

$f(\mathtt{11})=2$，因为存在两种可行的“好扩展”：101 和 111。

$f(\mathtt{01})=1$，因为仅存在一种可行的“好扩展”：011。