给定一个长度为 $n$ 的 $01$ 串,问有多少种划分,使得每一个划分出来的子串的 $1$ 的个数组成的序列是回文的,答案对 $998244353$ 取模。
输入格式
第一行一个正整数 $n$,表示 $01$ 串的长度。
第二行为一个长度为 $n$ 的 $01$ 串
输出格式
合法的划分方案数对 $998244353$ 取模的值。
样例输入
3
101
样例输出
4
样例解释
合法的划分方案为:$[101],[10,1],[1,01],[1,0,1]$,其中 $1$ 的个数组成的序列为 $[2],[1,1],[1,1],[1,0,1]$,这些序列都是回文的。
数据规模
$1\leq n\leq 2500$
- 进阶:思考一下 $O(n)$ 做法