题目描述

Nephren向来不喜欢冗长的告别。在Chtholly动身去执行下一项任务之前，她一言不发，转而准备一条小小的丝带送给她。

她在桌上将 $n$ 颗玻璃珠子摆成一排，之后把它们串到丝带上。每一颗珠子是白色或者黑色。用一个二进制字符串 $s$ 表示珠子的颜色：字符 $0$ 代表白色珠子，字符 $1$ 代表黑色珠子。

为了让排布不那么普通，Nephren把这件事变成了一个小游戏。她可以执行下面的操作任意次（可以是 $0$ 次）：

• 选定两个下标 $l$ 和 $r$（$(l<r)$），满足当前字符串中 $s_l=s_r$，将子串 $s[l \dots r]$ 翻转。

举个例子，如果 $(s=00110)$，Nephren可以选 $(l=1)$，$(r=5)$，因为 $s_1=s_5=0$。操作之后字符串变为 $01100$。

求从初始串 $s$ 出发，能够得到多少种互不相同的二进制字符串。答案可能很大，请输出答案对 $998244353$ 取模后的结果。

注：二进制字符串指每一个字符只能是 $0$ 或者 $1$ 的字符串。 翻转子串 $s[l\dots r]$，就是把它替换成 $s_r s_{r-1} \dots s_l$。

输入

每个测试点包含多组测试用例。第一行输入测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来给出各组测试用例。

每组测试用例第一行输入一个整数 $n$（$1 \le n \le 2\cdot 10^5$），代表珠子的数量。

第二行输入长度为 $n$ 的二进制字符串 $s$，描述珠子的颜色。

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

输出

对每一组测试用例，输出一个整数：从初始串 $s$ 可以得到的不同二进制字符串的数量，对 $998244353$ 取模。

样例

4
5
00110
6
001010
5
01010
6
111111

2
3
1
1

说明

第一组测试用例，仅可以得到下面两个字符串：

• $00110$；
• $01100$。

例如翻转整个字符串 $00110$ 就可以得到 $01100$。

第二组测试用例，仅可以得到下面三个字符串：

• $001010$；
• $010010$；
• $010100$。

例如 $010010$ 可以通过翻转 $001010$ 的前四个字符得到；$010100$ 可以翻转整个 $001010$ 得到。

第三组测试用例中，所有两端字符相等的子串本身都是回文串。因此任意合法翻转都不会改变字符串，仅能得到原串 $01010$。

第四组测试用例，只能得到 $111111$。

原题链接

原题链接