平衡分段

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定一个长度为 $n$ 的非负整数数组 $a$。

把数组划分成若干个非空连续段。设各段元素和依次为 $s_1,s_2,\ldots,s_k$。如果这个序列是回文的，即对所有 $1\le i\le k$ 都有 $s_i=s_{k-i+1}$，则称这种划分是平衡的。

请计算平衡划分的方案数。两个划分不同，当且仅当它们的切分位置集合不同。答案对 $998244353$ 取模。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据包含两行：

• 第一行一个整数 $n$；
• 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每组测试数据输出一行一个整数，表示平衡划分的方案数对 $998244353$ 取模后的结果。

样例输入

6
1
1000000000
2
1 1
4
0 0 1 0
5
1 2 3 2 1
5
1 3 5 7 9
32
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例输出

1
2
3
4
2
150994942

数据范围

对所有测试数据：

• $1\le t\le 10^5$；
• $1\le n\le 10^5$；
• $0\le a_i\le 10^9$；
• 所有测试数据的 $n$ 之和不超过 $10^5$。