## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Chef And Division CodeChef Solution | CodeChef Problem Solution 2022

You are given an array $A$ of size $N$.

A partitioning of the array $A$ is the splitting of $A$ into one or more non-empty contiguous subarrays such that each element of $A$ belongs to exactly one of these subarrays.

Find the number of ways to partition $A$ such that the parity of the sum of elements within the subarrays is alternating. In other words, if ${S}_{i}$ denotes the sum of the elements in the $i$-th subarray, then either

• ${S}_{1}$ is odd, ${S}_{2}$ is even, ${S}_{3}$ is odd and so on.
• or ${S}_{1}$ is even, ${S}_{2}$ is odd, ${S}_{3}$ is even and so on.

For example if $A=\left[1,2,3,3,5\right]$. One way to partition $A$ is $\left[1,2\right]\left[3,3\right]\left[5\right]$. Another way to partition $A$ is $\left[1\right]\left[2\right]\left[3\right]\left[3,5\right]$. Note that there exists more ways to partition this array.

Solution Click Below:-

Since the answer may be large, output it modulo $998244353$.

### Input Format

• The first line contains a single integer $T$ - the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ - the size of the array $A$.
• The second line of each test case contains $N$ space-separated integers ${A}_{1},{A}_{2},\dots ,{A}_{N}$ denoting the array $A$.

### Output Format

For each test case, output the answer modulo $998244353$.

### Constraints

• $1\le T\le 10000$
• $1\le N\le 2\cdot {10}^{5}$
• $0\le {A}_{i}\le {10}^{9}$
• Sum of $N$ over all test cases does not exceed $2\cdot {10}^{5}$

### Sample Input 1

3
3
1 2 3
4
4 4 4 4
5
1 2 3 3 5


### Sample Output 1

2
1
5


### Explanation

Test case 1: The array can be partitioned as follows

• $\left[1\right]\left[2\right]\left[3\right]$
• $\left[1,2,3\right]$

Test case 2: The array can be partitioned as follows