[R72F]划分 - 代码源竞赛平台

时空限制

2S/512M

题目描述

给定一个长度为 $n$ 的二进制字符串 $s$，下标从 $1$ 开始。

你需要将下标集合 $\{1,2,\ldots,n\}$ 划分为若干个非空集合，使每个下标恰好属于其中一个集合。对于划分中的每个集合 $A$，均需要满足

$$s_{\min(A)}=s_{\max(A)}.$$

其中，$\min(A)$ 和 $\max(A)$ 分别表示集合 $A$ 中最小和最大的元素。

若两个划分包含的集合完全相同，则视为同一种划分，不考虑这些集合的排列顺序。求满足条件的划分数量。由于答案可能很大，请对 $998244353$ 取模。

格式

输入格式

第一行包含一个正整数 $n$，表示字符串长度。

第二行包含一个长度为 $n$ 的字符串 $s$，其中每个字符均为 0 或 1。

输出格式

输出一个整数，表示满足条件的划分数量对 $998244353$ 取模后的结果。

样例

样例输入 #1

3
010

样例输出 #1

3

样例解释 #1

三种合法划分分别为

$$\{\{1\},\{2\},\{3\}\},\quad \{\{1,3\},\{2\}\},\quad \{\{1,2,3\}\}.$$

样例输入 #2

10
0000000000

样例输出 #2

115975

样例输入 #3

10
0100111010

样例输出 #3

15255

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	特殊性质
$1$	$30$	特殊性质 A
$2$	$70$	无

特殊性质 A：对于任意 $1\le i,j\le n$，均有 $s_i=s_j$。

对于 $100\%$ 的数据，满足 $1\le n\le 300$；对于任意 $1\le i\le n$，均有 $s_i\in\{\texttt{0},\texttt{1}\}$。