该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

l10k暑假在健身。健身房有活动，只要连续健身，就只收一天的钱。l10k回忆暑假的健身情况，如果健身了用1表示，没健身用0表示，想不起来就用-1表示。这些记录下来的数字实际上形成了一个长度为 n 的数组：$[a1, a2, . . . , an] (∀1 ≤ i ≤ n, 0 ≤ a_i ≤ 1)$，其中$a_i$表示l10k 第 i天有无健身。 然而，随着时间的推移，一些写下的数字变得模糊不清，你无法判断它是 1 还是 0。如果有 k 个数字无 法识别，则可能有 2k 种不同的数组。 对于每个可能的数组，你都可以依据这个数组计算l10k的连续健身次数。如果将可能的不同连续健身次数结果相加，得到的结果如何呢？由于答案可能很大，请将结果关于998244353取模后输出。

输入格式

每组测试包含多个测试用例。 第一行是测试用例的数量 $T (1 ≤ T ≤ 104 )$。 每个测试用例由两行组成。 第一行包含一个整数$n (2 ≤ n ≤ 5 × 105 )$，表示笔记的数量。 第二行包含 $n$ 个整数$a_1, a_2, . . . , a_n (−1 ≤ a_i ≤ 1)$ ，表示每个记录下来的数字。只有当 $a_i = −1$ 时，数 字是未知的。 可以保证单组测试中， $\Sigma n$ 不会超过$5 × 10^5$。

输出格式

对于每个测试用例，输出 1 个整数 —— 不同数组的连续健身次数求和后，对 998244353 取模的结果。

输入输出样例

3
3
1 0 1
3
0 0 0
3
1 -1 1

2 
0
3

提示

在第一个测试用例中，当l10k记录第一个和第三个数字 1 时，他健身一定是两个连续次。 在第二个测试用例中，l10k从未健身，因此答案是 0。 在第三个测试用例中，数组可能是$$[1, 1, 1] 或 [1, 0, 1]$。如果数组是$[1, 1, 1]$，那么l10k连续健身`1`次，因此结果是 `1`。如果数组是$[1, 0, 1]$，那么与第一个测试用例一致，结果为2。将两种情况的答案求和，结果是$1 + 2 = 3$。