A16578 | Affectionate Arrays (Hard Version)

你是信的开头，诗的内容，童话的结尾。

— ilem, [勾指起誓](https://www.bilibili.com/video/BV1Jb411U7u2/)

本题是困难版问题。两个版本的区别在于，此版本中你需要计算不同数组的数量。

Iris 珍视一个整数数组 $a_1, a_2, \ldots, a_n$。她知道这个数组有一个有趣的性质：所有元素的最大绝对值不超过所有元素的和，即 $\max(\lvert a_i\rvert) \leq \sum a_i$。

Iris 定义数组的**无聊值**为其最大子数组$^{\text{∗}}$和。

Iris 的生日即将到来，Victor 打算送她另一个数组 $b_1, b_2, \ldots, b_m$ 作为礼物。出于某些看似明显的原因，他决定数组 $b_1, b_2, \ldots, b_m$ 应满足以下条件：

- $a_1, a_2, \ldots, a_n$ 必须是 $b_1, b_2, \ldots, b_m$ 的子序列$^{\text{†}}$。
- 两个数组的和相同，即 $\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^m b_i$。
- 数组 $b$ 的无聊值尽可能小。
- 在所有具有最小无聊值的数组中，数组 $b$ 的长度（即 $m$）尽可能小。此时，Iris 将立刻理解他的心意！

即使有上述约束，可能的礼物仍然太多。因此 Victor 请你计算满足所有条件的数组 $b_1, b_2, \ldots, b_m$ 的数量。由于答案可能很大，只需输出对 $998\,244\,353$ 取模的结果。他承诺：如果你成功帮助他，他会与你分享 Iris 的生日蛋糕。

注意：由于输入规模较大，你可能需要针对此问题进行优化。

例如，在 C++ 中，只需在 main() 函数开头添加以下代码：

```cpp
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
}
```

$^{\text{∗}}$ 若数组 $c$ 可通过删除数组 $d$ 开头和末尾的若干（可能为零或全部）元素得到，则称 $c$ 是 $d$ 的子数组。

$^{\text{†}}$ 若序列 $c$ 可通过删除序列 $d$ 中任意位置的若干（可能为零或全部）元素得到，则称 $c$ 是 $d$ 的子序列。

每个测试包含多个测试用例。第一行输入一个整数 $t$（$1 \leq t \leq 10^5$）—— 测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 3\times 10^6$）—— 数组 $a_1, a_2, \ldots, a_n$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$）—— 初始数组。保证 $\max(\lvert a_i\rvert) \leq \sum a_i$。

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

对每个测试用例，输出一行一个整数：满足条件的数组 $b$ 的数量对 $998\,244\,353$ 取模后的结果。