让我们调用一个整数序列 自产 如果对于每个 $$$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$$$ 为模。
示例
输入复制
531 1 220 050 1 0 1 061 0 2 2 1 1112 0 3 1 0 0 2 3 0 3 2
输出复制
2412841