子串（数据加强版）

题目描述

给定一个长度为 $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)$ 做法