← 返回题目列表

Codeforces · 2199/F

F. 自制序列

中文机器翻译题面 查看原题

让我们调用一个整数序列 自产 如果对于每个 $$$i$$$ ($$$1 \le i \le n$$$) 至少满足以下条件之一:

  • $$$a_i$$$ 等于左侧元素的总和(即 $$$a_i = \displaystyle\sum\limits_{j = 1}^{i - 1} a_j$$$);
  • $$$a_i$$$ 等于右侧元素的总和(即 $$$a_i = \displaystyle\sum\limits_{j = i + 1}^{n} a_j$$$)。

请注意,序列开头/结尾的 $$$0$$$ 也被认为是有效的。

给定一个整数数组 $$$a$$$,大小为 $$$n$$$。你的任务是计算数组 $$$a$$$ 的自生成子序列的数量。由于答案可能很大,因此打印它对 $$$998244353$$$ 取模。如果所选元素的索引不同,则两个子序列不同。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 数组 $$$a$$$ 自生成的子序列数以 $$$998244353$$$ 为模。

示例

输入
复制

5
3
1 1 2
2
0 0
5
0 1 0 1 0
6
1 0 2 2 1 1
11
2 0 3 1 0 0 2 3 0 3 2

输出
复制

2
4
12
8
41