Description: The two versions of the problem are different. You may want to read both versions. You can make hacks only if both versions are solved. You are given an array $$$a$$$ of length $$$n$$$. Start with $$$c = 0$$$. Then, for each $$$i$$$ from $$$1$$$ to $$$n$$$ (in increasing order) do exactly one of the following: - Option $$$1$$$: set $$$c$$$ to $$$c + a_i$$$. - Option $$$2$$$: set $$$c$$$ to $$$|c + a_i|$$$, where $$$|x|$$$ is the absolute value of $$$x$$$. Let the maximum final value of $$$c$$$ after the procedure described above be equal to $$$k$$$. Find the number of unique procedures that result in $$$c = k$$$. Two procedures are different if at any index $$$i$$$, one procedure chose option $$$1$$$ and another chose option $$$2$$$, even if the value of $$$c$$$ is equal for both procedures after that turn. Since the answer may be large, output it modulo $$$998\,244\,353$$$. Input Format: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$). The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$). The sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$. Output Format: For each test case, output a single integer — the number of unique procedures that result in $$$c = k$$$, modulo $$$998\,244\,353$$$. Note: 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.