题目描述
给定一个长度为 n 的二进制字符串 s。
可以进行任意次(包括 0 次)以下操作:
- 选择两个下标 l,r,满足 1≤l≤r≤n 且 sl=sr;
- 将子串 slsl+1…sr 翻转。
求通过上述操作能够得到的不同二进制字符串数量,答案对 998244353 取模。
子串翻转是指将 slsl+1…sr 替换为 srsr−1…sl。
例如,如果 s=00110,可以选择 l=1 和 r=5,因为 s1=s5=0。执行操作后,字符串变成 01100。
输入格式
第一行包含一个整数 n,表示字符串长度。
第二行包含一个长度为 n 的二进制字符串 s。
输出格式
输出一行一个整数,表示结果对 998244353 取模后的值。
样例 1 输入
6
001010
样例 1 输出
3
样例 1 解释
在这个样例中,恰好能获得如下三个字符串:
数据范围
对于所有测试数据,保证:1≤n≤106。
| 测试点 |
n≤ |
特殊性质 |
| 1∼4 |
8 |
无 |
| 5∼6 |
20 |
| 7∼8 |
1000 |
| 9∼11 |
106 |
存在 i≤j,使得 [i,j] 内全为 1,区间外全为 0 |
| 12∼14 |
不存在两个相邻的 1 |
| 15∼20 |
无 |