CF2255B.A Ribbon for Tomorrow

Nephren has never been fond of long farewells. Before Chtholly leaves for her next mission, she says nothing and begins preparing a small ribbon for her instead.

She places $n$ glass beads in a row on the table before threading them onto the ribbon. Each bead is either white or black. A binary$^{\text{∗}}$ string $s$ represents their colors: the character $\mathtt{0}$ represents a white bead, and the character $\mathtt{1}$ represents a black bead.

To make the arrangement less ordinary, Nephren turns it into a small game. She can perform the following operation any number of times (possibly zero):

• Choose two indices $l$ and $r$ ($1 \le l \le r \le n$) such that $s_l=s_r$ in the current string, and reverse$^{\text{†}}$ the substring $s_l s_{l+1}\ldots s_r$.

For example, if $s=\mathtt{00110}$, Nephren may choose $l=1$ and $r=5$, since $s_1=s_5=\mathtt{0}$. After the operation, the string becomes $\mathtt{01100}$.

Determine the number of different binary strings that can be obtained from $s$. Since this number may be large, output it modulo $998\,244\,353$.

$^{\text{∗}}$A binary string is a string where each character is either $\mathtt 0$ or $\mathtt 1$.

$^{\text{†}}$To reverse a substring $s_l s_{l+1}\ldots s_r$ means to replace it with $s_r s_{r-1}\ldots s_l$.

涅芙莲向来不喜欢漫长的告别。在克洛伊出发执行下一次任务之前，她什么也没说，而是开始为她准备一条小小的丝带。

她先把 $n$ 颗玻璃珠排成一列放在桌上，再将它们穿到丝带上。每颗珠子非白即黑。一个二进制$^{\text{∗}}$字符串 $s$ 表示它们的颜色：字符 $\mathtt{0}$ 代表白色珠子，字符 $\mathtt{1}$ 代表黑色珠子。

为了让排列不那么寻常，涅芙莲将其变成一个小游戏。她可以执行以下操作任意多次（包括零次）：

• 选择两个下标 $l$ 和 $r$（满足 $1 \le l \le r \le n$），使得当前字符串中 $s_l = s_r$，然后将子串 $s_l s_{l+1}\ldots s_r$ 翻转$^{\text{†}}$。

例如，若 $s = \mathtt{00110}$，涅芙莲可选取 $l = 1$ 和 $r = 5$，因为 $s_1 = s_5 = \mathtt{0}$。执行操作后，字符串变为 $\mathtt{01100}$。

求从 $s$ 出发能够得到的不同二进制字符串的总数。由于该数可能很大，请输出其对 $998\,244\,353$ 取模的结果。

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

$^{\text{†}}$ 将子串 $s_l s_{l+1}\ldots s_r$ 翻转，是指将其替换为 $s_r s_{r-1}\ldots s_l$。

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$ ($1 \le n \le 10^6$) — the number of beads.

The second line contains a binary string $s$ of length $n$, describing the colors of the beads.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

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

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 表示珠子的数量。

第二行包含一个长度为 $n$ 的二进制字符串 $s$，用于描述珠子的颜色。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

For each test case, output a single integer — the number of different binary strings that can be obtained from $s$, modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——即可以从 $s$ 得到的不同二进制字符串的数目，对 $998\,244\,353$ 取模。

In the first test case, exactly the following two strings can be obtained:

• $\mathtt{00110}$;
• $\mathtt{01100}$.

For example, reversing the entire string $\mathtt{00110}$ produces $\mathtt{01100}$.

In the second test case, exactly the following three strings can be obtained:

• $\mathtt{001010}$;
• $\mathtt{010010}$;
• $\mathtt{010100}$.

For example, $\mathtt{010010}$ can be obtained by reversing the first four characters of $\mathtt{001010}$, and $\mathtt{010100}$ can be obtained by reversing the entire string $\mathtt{001010}$.

In the third test case, every substring whose endpoints contain the same character is a palindrome. Therefore, reversing any valid substring does not change the string, and only $\mathtt{01010}$ can be obtained.

In the fourth test case, we can only get $\mathtt{111111}$.

在第一个测试用例中，恰好可以得到以下两个字符串：

• $\mathtt{00110}$；
• $\mathtt{01100}$。

例如，将整个字符串 $\mathtt{00110}$ 反转可得到 $\mathtt{01100}$。

在第二个测试用例中，恰好可以得到以下三个字符串：

• $\mathtt{001010}$；
• $\mathtt{010010}$；
• $\mathtt{010100}$。

例如，$\mathtt{010010}$ 可通过对 $\mathtt{001010}$ 的前四个字符进行反转得到；而 $\mathtt{010100}$ 可通过对整个字符串 $\mathtt{001010}$ 进行反转得到。

在第三个测试用例中，所有端点字符相同的子串均为回文串。因此，对任意合法子串进行反转均不会改变原字符串，故仅能得到 $\mathtt{01010}$。

在第四个测试用例中，我们只能得到 $\mathtt{111111}$。