给定一个长度为 $$$n$$$ 的整数序列 $$$a_1, a_2, \dots, a_n$$$,你的任务是计算以 $$$998244353$$$ 为模的方法将其划分为几个非空连续子序列,以便子序列中的元素之和形成一个平衡序列。
如果对于每个 $$$1 \leq i \leq k$$$,$$$s_{i} = s_{k-i+1}$$$,则长度为 $$$k$$$ 的序列 $$$s_1, s_2, \dots, s_k$$$ 被认为是平衡的。例如,$$$[1, 2, 3, 2, 1]$$$ 和 $$$[1,3,3,1]$$$ 是平衡的,但 $$$[1,5,15]$$$ 不是平衡的。
形式上,每个分区都可以通过长度为 $$$k$$$ 的索引序列 $$$i_1, i_2, \dots, i_k$$$ 来描述,其中 $$$1 = i_1 < i_2 < \dots < i_k \leq n$$$ 使得
1、$$$k$$$是分区中非空连续子序列的数量;
2. 对于每个 $$$1 \leq j \leq k$$$,第 $$$j$$$ 个连续子序列以 $$$a_{i_j}$$$ 开始,并在 $$$a_{i_{j+1}}$$$ 之前结束,其中 $$$i_{k+1} = n + 1$$$。也就是说,第 $$$j$$$ 个子序列是 $$$a_{i_j}, a_{i_j+1}, \dots, a_{i_{j+1}-1}$$$。
令 $$$s_1, s_2, \dots, s_k$$$ 表示关于分区 $$$i_1, i_2, \dots, i_k$$$ 的子序列中的元素之和。形式上,对于每个$$$1 \leq j \leq k$$$,$$$$$$ s_j = \sum_{i=i_{j}}^{i_{j+1}-1} a_i = a_{i_j} + a_{i_j+1} + \dots + a_{i_{j+1}-1}。 $$$$$$ 例如,序列$$$[1,2,3,4,5,6]$$$的分区$$$[1\,|\,2,3\,|\,4,5,6]$$$由索引序列$$$[1,2,4]$$$描述,关于该分区的子序列中的元素之和为$$$[1,5,15]$$$。
如果以下至少一项成立,则两个分区 $$$i_1, i_2, \dots, i_k$$$ 和 $$$i'_1, i'_2, \dots, i'_{k'}$$$ (由索引序列描述)被认为是不同的。
- $$$k \neq k'$$$,
- $$$i_j \neq i'_j$$$ 对于某些 $$$1 \leq j \leq \min\left\{ k, k' \right\}$$$。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。以下行包含每个测试用例的描述。
每个测试用例的第一行包含一个整数$$$n$$$ ($$$1 \leq n \leq 10^5$$$),表示序列$$$a$$$的长度。
每个测试用例的第二行包含$$$n$$$整数$$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$),表示序列$$$a$$$的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出每个子序列中元素之和平衡的分区数,以 $$$998244353$$$ 为模。
示例
输入 #1
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
1 2 3 4 2 150994942
注意
对于第一个测试用例,只有一种方法可以对长度为 $$$1$$$ 的序列进行分区,它本身就是平衡的。
对于第二个测试用例,有 $$$2$$$ 对其进行分区的方法:
- 序列 $$$[1, 1]$$$ 本身,则 $$$s = [2]$$$ 是平衡的;
- 划分为两个子序列 $$$[1\,|\,1]$$$,则 $$$s = [1, 1]$$$ 是平衡的。
对于第三个测试用例,有 $$$3$$$ 对其进行分区的方法:
- 序列 $$$[0, 0, 1, 0]$$$ 本身,则 $$$s = [1]$$$ 是平衡的;
- $$$[0 \,|\, 0, 1 \,|\, 0]$$$,则 $$$s = [0, 1, 0]$$$ 平衡;
- $$$[0, 0 \,|\, 1 \,|\, 0]$$$,则 $$$s = [0, 1, 0]$$$ 是平衡的。
对于第四个测试用例,有 $$$4$$$ 对其进行分区的方法:
- 序列 $$$[1, 2, 3, 2, 1]$$$ 本身,则 $$$s = [9]$$$ 是平衡的;
- $$$[1, 2 \,|\, 3 \,|\, 2, 1]$$$,则 $$$s = [3, 3, 3]$$$ 平衡;
- $$$[1 \,|\, 2, 3, 2 \,|\, 1]$$$,则 $$$s = [1, 7, 1]$$$ 平衡;
- $$$[1 \,|\, 2 \,|\, 3 \,|\, 2 \,|\, 1]$$$,则 $$$s = [1, 2, 3, 2, 1]$$$ 是平衡的。
对于第五个测试用例,有 $$$2$$$ 对其进行分区的方法:
- 序列 $$$[1, 3, 5, 7, 9]$$$ 本身,则 $$$s = [25]$$$ 是平衡的;
- $$$[1, 3, 5 \,|\, 7 \,|\, 9]$$$,则 $$$s = [9, 7, 9]$$$ 是平衡的。
对于第六个测试用例,应计算每个可能的分区。所以答案是$$$2^{32-1} \equiv 150994942 \pmod {998244353}$$$。