给定一个长度为 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≤n≤2500