CF2199F Self-Produced Sequences

Let's call an integer sequence self-produced if for every $ i $ ( $ 1 \le i \le n $ ) at least one of the following conditions holds: - $ a_i $ is equal to the sum of the elements on the left (i. e. $ a_i = \displaystyle\sum\limits_{j = 1}^{i - 1} a_j $ ); - $ a_i $ is equal to the sum of the elements on the right (i. e. $ a_i = \displaystyle\sum\limits_{j = i + 1}^{n} a_j $ ). Note that $ 0 $ at the beginning/end of the sequence is also considered valid. You are given an integer array $ a $ of size $ n $ . Your task is to calculate the number of self-produced subsequences of the array $ a $ . Since the answer might be large, print it modulo $ 998244353 $ . Two subsequences are different if the indices of chosen elements are different.

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 10^9 $ ). Additional constraint on the input: the sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

For each test case, print a single integer — the number of self-produced subsequences of the array $ a $ taken modulo $ 998244353 $ .