CF1984C2.Magnitude (Hard Version)

注意： 本题的两个版本题意是有不同的，你可能需要同时阅读两个版本的题意。

给定一个长度为 $n$ 的数组 $a$。初始有 $c=0$；接下来，对每个在 $1$ 到 $n$ 范围内的 $i$（按递增的顺序） ，要执行以下两种操作中的恰好一种：

• 操作 $1$：将 $c$ 修改为 $c+a_i$。

• 操作 $2$：将 $c$ 修改为 $|c+a_i|$，这里 $|x|$ 表示 $x$ 的绝对值。

令所有操作后 $c$ 能取得的最大值为 $k$，你需要求出有多少种本质不同的方案使得 $c=k$。这里两个方案被视为不同，当且仅当存在一个 $i$ 使得其中一个方案选了操作 $1$ 而另一个选了操作 $2$，即便这步操作后两个方案对应的 $c$ 相等。

由于答案可能很大，请输出答案对 $998244353$ 取模后的结果。

第一行为一个正整数 $t\;(1\leq t\leq 10^4)$，表示测试数据的组数。

接下来的每组测试数据，第一行为一个正整数 $n\;(1\leq n\leq 2\cdot10^5)$，

第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n\;(-10^9\leq a_i\leq 10^9)$。

对每组测试数据，输出一个整数，表示本质不同的方案数对 $998244353$ 取模的结果。

保证所有测试数据的 $n$ 之和不超过 $3\cdot10^5$。