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$。

In the first test case, it can be shown that our maximal final value of $ c $ is $ 3 $ . There are $ 12 $ ways to achieve this because in order to get $ 3 $ , we have to take absolute value at indices $ 2 $ or $ 4 $ , or both, resulting in $ 3 $ ways. For the other two indices, it doesn't change the value whether we take absolute value or not, so we have $ 2 \cdot 2 = 4 $ ways for them. In total, we have $ 3 \cdot 4 = 12 $ ways. In the second test case, taking the absolute value will never change anything, so we can either take absolute value or not, for every index. This gives us $ 2^8 = 256 $ possible ways.