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 = [1, 2, 3, 3, 5]. One way to partition A is [1, 2] [3, 3] [5]. Another way to partition A is [1] [2] [3] [3, 5]. Note that there exists more ways to partition this array.

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 ≤ T ≤ 10000$
$1 ≤ N ≤ 2 \cdot 10^{5} $
$0 ≤ A_{i} ≤ 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 1 ------ 
Test case 1: The array can be partitioned as follows
- $[1] [2] [3]$
- $[1, 2, 3]$

Test case 2: The array can be partitioned as follows
- $[4, 4, 4, 4]$

Difficulty: VERY_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 998244353
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	length = int(input())
	arr = [int(x) for x in input().split()]
	parities = [x & 1 for x in arr]
	if length == 1:
		print(1)
		continue

	@lru_cache(None)
	def DP(i, sum_parity, prev_sum_parity):
		if i == length:
			return 0 if sum_parity == prev_sum_parity else 1
		ret = DP(i + 1, sum_parity ^ parities[i], prev_sum_parity)
		if sum_parity != prev_sum_parity:
			ret += DP(i + 1, parities[i], sum_parity)
		return ret % mod
	ans = DP(1, parities[0], None)
	print(ans)
	DP.cache_clear()


MOD = 998244353

def solve(A, N):
	dp = [[0] * 2 for i in range(N + 1)]
	cur_sm = 0
	(oPrefEven, oPrefOdd) = (0, 0)
	(ePrefEven, ePrefOdd) = (0, 0)
	for (i, it) in enumerate(A):
		ind = i + 1
		cur_sm += it
		cur_sm %= 2
		if cur_sm % 2:
			dp[ind][1] += 1
			dp[ind][1] += ePrefEven
			dp[ind][0] += oPrefOdd
		else:
			dp[ind][0] += 1
			dp[ind][0] += ePrefOdd
			dp[ind][1] += oPrefEven
		dp[ind][0] %= MOD
		dp[ind][1] %= MOD
		if cur_sm:
			oPrefEven += dp[ind][0]
			oPrefOdd += dp[ind][1]
		else:
			ePrefEven += dp[ind][0]
			ePrefOdd += dp[ind][1]
	return sum(dp[N]) % MOD
for case in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	print(solve(A, N))


import sys
M = 998244353
from collections import defaultdict

def solve(a, n, s, p, dp):
	key = str(n) + ':' + str(s % 2) + ':' + str(p)
	if n < 0 and s % 2 == p:
		return 1
	if n < 0:
		return 0
	if dp[key] != 0:
		return dp[key]
	if s % 2 == p:
		ans = solve(a, n - 1, s + a[n], p, dp) % M + solve(a, n - 1, a[n], not p, dp) % M
		dp[key] = ans % M
		return dp[key]
	dp[key] = solve(a, n - 1, s + a[n], p, dp) % M
	return dp[key] % M
for _ in range(int(input())):
	n = int(input())
	dp = defaultdict(int)
	sys.setrecursionlimit(10 ** 7)
	a = list(map(int, input().split()))
	ans = solve(a, n - 2, a[n - 1], True, dp) % M
	p = solve(a, n - 2, a[n - 1], False, dp) % M
	print((p + ans) % M)


M = 998244353
from collections import defaultdict

def fs(n, a):
	dp = defaultdict(int)
	dp[-1, 0, 0] = 1
	dp[-1, 1, 1] = 1
	for i in range(n):
		for k in range(2):
			for j in range(2):
				if j == k:
					dp[i, j, k] = (dp[i - 1, (j + a[i]) % 2, k] % M + dp[i - 1, a[i] % 2, 1 - k] % M) % M
				else:
					dp[i, j, k] = dp[i - 1, (j + a[i]) % 2, k] % M
	return (dp[n - 2, a[n - 1] % 2, 1] + dp[n - 2, a[n - 1] % 2, 0]) % M
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = fs(n, a) % M
	print(f)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if l[0] % 2 == 0:
		oe = 1
		ee = 1
		oo = 0
		eo = 0
		en = 1
		on = 0
	else:
		ee = 0
		oe = 0
		eo = 1
		oo = 1
		en = 0
		on = 1
	for i in l[1:]:
		if i % 2 == 0:
			(oo, eo, oe, ee, en, on) = (oo, eo, oe + on, ee + en, oe + on, eo)
		else:
			(oo, eo, oe, ee, en, on) = (oe + on, ee + en, oo, eo, oo, en + ee)
	print((en + on) % 998244353)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	mod = 998244353
	dp = [1, 1]
	s = [[1, 1], [0, 0]]
	p = 0
	for i in a:
		p ^= i & 1
		dp[0] = s[p][1]
		dp[1] = s[p ^ 1][0]
		s[p][0] += dp[0]
		s[p][1] += dp[1]
		s[p][0] %= mod
		s[p][1] %= mod
	print((dp[0] + dp[1]) % mod)


import math
mod1 = 998244353
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.insert(0, 0)
	arr = [[[0, 0] for i in range(2)] for j in range(n + 1)]
	arr[0][1][0] = 1
	for i in range(1, n + 1):
		x = l[i] & 1
		arr[i][0][x] = (arr[i][0][x] + arr[i - 1][1][0]) % mod1
		arr[i][1][x] = (arr[i][1][x] + arr[i - 1][0][1]) % mod1
		arr[i][0][0 ^ x] = (arr[i][0][0 ^ x] + arr[i - 1][0][0]) % mod1
		arr[i][0][1 ^ x] = (arr[i][0][1 ^ x] + arr[i - 1][0][1]) % mod1
		arr[i][1][0 ^ x] = (arr[i][1][0 ^ x] + arr[i - 1][1][0]) % mod1
		arr[i][1][1 ^ x] = (arr[i][1][1 ^ x] + arr[i - 1][1][1]) % mod1
	print((arr[n][1][0] + arr[n][0][1]) % mod1)


from sys import stdin, gettrace
MOD = 998244353

def solve():
	n = int(input())
	aa = [int(a) for a in input().split()]
	e = 1 - aa[0] % 2
	o = aa[0] % 2
	ee = eo = oe = oo = 0
	for a in aa[1:]:
		if a % 2 == 0:
			(e, o, ee, eo, oe, oo) = (e, o, ee + oe + e, eo, eo + oe + o, oo)
		else:
			(e, o, ee, eo, oe, oo) = (o, e, eo, ee + oe + e, oo, eo + oe + o)
		e %= MOD
		o %= MOD
		ee %= MOD
		eo %= MOD
		oe %= MOD
		oo %= MOD
	print((eo + oe + e + o) % MOD)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mod = 998244353
	dp = []
	dit = {}
	idx = -1
	curr = 0
	check = []
	for i in range(n):
		curr = curr + (arr[i] & 1) & 1
		check.append(curr)
		if arr[i] & 1:
			dit[idx] = i
			idx = i
	dit[idx] = float('inf')
	for i in range(n):
		dp.append([0, 0])
	dp.append([1, 1])
	dp[-2] = [arr[-1] & 1 == 0, arr[-1] & 1]
	ans_0 = 0
	ans_1 = 0
	if check[n - 1] & 1:
		ans_1 = 1
	else:
		ans_0 = 1
	for i in range(n - 2, -1, -1):
		if check[i] & 1:
			ans_1 = (ans_1 + dp[i + 1][0]) % mod
		else:
			ans_0 = (ans_0 + dp[i + 1][0]) % mod
		if arr[i] & 1:
			odd = 0
			if check[i] == 1:
				odd = ans_1
			else:
				odd = ans_0
			even = 0
			if i in dit and dit[i] != float('inf'):
				if dit[i] != n - 1:
					even = dp[dit[i] + 1][0] + dp[dit[i] + 1][1]
				else:
					even = 1
		else:
			odd = dp[i + 1][1]
			even = dp[i + 1][1] + dp[i + 1][0]
		dp[i][0] = even % mod
		dp[i][1] = odd % mod
	print((dp[0][0] + dp[0][1]) % mod)


mod = 998244353
T = int(input())
for _ in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	odd = []
	even = []
	for i in range(N + 2):
		odd.append(None)
		even.append(None)
	odd[N + 1] = 0
	even[N + 1] = 0
	odd[N] = 0
	even[N] = 1
	j = N
	tmp = 0
	for i in range(N - 1, -1, -1):
		x = a[i] % 2
		if x == 0:
			odd[i] = odd[i + 1]
			even[i] = (odd[i + 1] + even[i + 1]) % mod
			tmp = (tmp + even[i]) % mod
		else:
			even[i] = (odd[j + 1] + even[j + 1]) % mod
			odd[i] = (tmp + even[j] + odd[j + 1]) % mod
			j = i
			tmp = 0
	answer = (odd[0] + even[0]) % mod
	print(answer)


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	dp = [[-1, -1, -1, -1] for i in range(N - 1)]
	if N == 1:
		print(1)
	elif N == 2:
		if A[0] % 2 == A[1] % 2:
			print(1)
		else:
			print(2)
	else:
		if A[0] % 2 == 0:
			dp[0][0] = 1
			dp[0][1] = 0
			dp[0][2] = 0
			dp[0][3] = 2
		else:
			dp[0][0] = 1
			dp[0][1] = 1
			dp[0][2] = 1
			dp[0][3] = 0
		for i in range(1, N - 1):
			if A[i] % 2 == 0:
				dp[i][0] = (dp[i - 1][0] + dp[i - 1][2]) % 998244353
				dp[i][1] = dp[i - 1][1]
				dp[i][2] = dp[i - 1][2]
				dp[i][3] = (dp[i - 1][3] + dp[i - 1][0]) % 998244353
			else:
				dp[i][0] = (dp[i - 1][3] + dp[i - 1][1]) % 998244353
				dp[i][1] = dp[i - 1][0]
				dp[i][2] = dp[i - 1][3]
				dp[i][3] = (dp[i - 1][2] + dp[i - 1][1]) % 998244353
		if A[N - 1] % 2 == 1:
			print((dp[N - 2][1] + dp[N - 2][3]) % 998244353)
		else:
			print((dp[N - 2][0] + dp[N - 2][2]) % 998244353)


from sys import stdin, stdout
input = stdin.readline
mod = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) % 2 for i in input().split()]
	dp = [[0, 0] for i in range(n)]
	dp[0][a[0] % 2] = 1
	run = a[0]
	vals = [[0, 0], [0, 0]]
	for i in range(1, n):
		if not a[i]:
			dp[i][0] = (dp[i - 1][1] + dp[i - 1][0]) % mod
			dp[i][1] = dp[i - 1][1]
		else:
			dp[i][0] = vals[run ^ 1][1]
			dp[i][1] = (vals[run][0] + dp[i - 1][0]) % mod
			dp[i][run ^ 1] += 1
		vals[run][0] = (vals[run][0] + dp[i - 1][0]) % mod
		vals[run][1] = (vals[run][1] + dp[i - 1][1]) % mod
		run = (run + a[i]) % 2
	print(sum(dp[-1]) % mod)