Substrings (Hard Version)

Problem Description

Given a $01$-string of length $n$, count the number of ways to partition it so that the sequence formed by the numbers of 1s in each resulting substring is a palindrome. Output the answer modulo $998244353$.

Input Format

The first line contains a positive integer $n$, the length of the $01$-string.

The second line contains a $01$-string of length $n$.

Output Format

The number of valid partition schemes, modulo $998244353$.

Sample Input

3
101

Sample Output

4

Sample Explanation

The valid partitions are: $[101], [10,1], [1,01], [1,0,1]$. The sequences of the numbers of 1s are $[2], [1,1], [1,1], [1,0,1]$, all of which are palindromes.

Constraints

$1 \le n \le 2500$

• Advanced: think about an $O(n)$ solution.