I2. 深情数组（困难版）

单个测试点时间限制：3 秒 内存限制：512 MB

你是字母的起笔，是诗篇的行文，是童话的句点。 —— ilem, 勾指起誓

注意：本题题面与官方比赛中使用的版本不同。本题题面已修正为可解版本，在官方比赛中，该题的所有提交已被移除。

这是该题的困难版本。两个版本的区别在于：在这个版本中，你需要计算所有合法数组的价值之和。只有当你解决了该题的所有版本时，你才可以进行 hack。

---

题目描述

艾瑞斯很珍爱一个整数数组 $a_1,a_2,\dots,a_n$。她知道这个数组拥有一个有趣的性质：所有元素的绝对值的最大值，不超过数组所有元素的和，即

$$\max(|a_i|) \le \sum_{i=1}^n a_i$$

艾瑞斯定义一个数组的无聊值为该数组的最大子段和。

艾瑞斯的生日快到了，维克托准备送她另一个数组 $b_1,b_2,\dots,b_m$ 作为礼物。他要求数组 $b$ 满足以下性质：

1. 数组 $a_1,a_2,\dots,a_n$ 是 $b_1,b_2,\dots,b_m$ 的一个子序列。
2. 两个数组的和相等，即 $\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^m b_i$。
3. 数组 $b$ 的无聊值尽可能小。
4. 在所有满足无聊值最小的数组 $b$ 中，数组 $b$ 的长度 $m$ 尽可能小。

对于一个满足上述所有条件的数组 $b$，维克托定义该数组的价值为：数组 $a$ 在 $b$ 中作为子序列出现的次数。 即统计满足 $1 \le c_1 < c_2 < \dots < c_n \le m$ 且对所有 $1 \le i \le n$ 都有 $b_{c_i}=a_i$ 的下标序列 $c$ 的数量。

即使有以上约束，符合条件的数组 $b$ 仍然有很多。请你计算所有合法数组 $b$ 的价值之和，答案对 $998244353$ 取模。

---

定义说明

$*$ 子段 (subarray)：数组 $c$ 是数组 $d$ 的子段，当且仅当从 $d$ 的开头删去若干（可零）个元素、从末尾删去若干（可零）个元素后可以得到 $c$。

$†$ 子序列 (subsequence)：序列 $c$ 是序列 $d$ 的子序列，当且仅当从 $d$ 中任意位置删去若干（可零）个元素后可以得到 $c$。

---

输入格式

输入包含多组测试数据。 第一行输入一个整数 $t$（$1 \le t \le 10^5$），表示测试用例数量。

每组测试用例：

• 第一行一个整数 $n$（$1 \le n \le 3\times10^6$），表示数组 $a$ 的长度。
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$-10^9 \le a_i \le 10^9$）。
• 保证满足约束：$\max(|a_i|) \le \sum a_i$。

保证所有测试用例的 $n$ 之和不超过 $3\times10^6$。

---

输出格式

对于每组测试用例，输出一行一个整数，表示所有合法数组 $b$ 的价值之和，对 $998244353$ 取模。

---

样例输入

5
4
1 2 3 4
4
2 -3 2 2
4
1 -2 2 1
10
2 -7 6 3 -1 4 2 -5 8 -4
20
4 -2 4 3 -2 1 5 2 3 6 -5 -1 -4 -2 -3 5 -3 1 -4 1

样例输出

1
2
2
20
1472

---

样例解释

1. 第一组：$a=[1,2,3,4]$ 唯一合法数组 $b$ 就是 $a$ 本身，价值为 $1$。

2. 第二组：$a=[2,-3,2,2]$ 合法 $b$ 有两个：$[1,2,-3,2,-1,2]$ 和 $[2,1,-3,2,-1,2]$。 每个 $b$ 的价值都是 $1$，总和为 $2$。

3. 第三组：$a=[1,-2,2,1]$ 唯一合法 $b$ 是 $[1,1,-2,2,-1,1]$。 $a$ 在 $b$ 中作为子序列出现 $2$ 次，价值为 $2$。