Problem Statement

‘Cause morning rolls around, and it’s another day of sun!

But as a sleep addict, Sean spends lots of hours sleeping, and thus, he can’t even remember which day it is when he wakes up.

So starting from someday, he started taking notes: when he wakes up, he writes a number about whether there’s sunlight outside. If there is, he will write a $1$ on it; otherwise, he will write a $0$ . And after taking notes, without enough time for sunlight to fade or for moonlight to dim, he falls asleep again. We assume that every time Sean wakes up, he sees either the sunlight or the moonlight, but not both.

So the notes actually form an array of length $n$ : $[a_1,a_2,\dots,a_n]\ (\forall 1\leq i\leq n, 0\leq a_i\leq 1)$ , where $a_i$ represents the $i$-th number Sean wrote.

However, as time goes on, some numbers written become ambiguous and are just impossible to identify, and you can’t really tell whether it is a $1$ or a $0$ . So if there are $k$ numbers that you can’t identify, there can be $2^k$ different arrays.

For each array, you can calculate the minimum number of days on which Sean sees the sunlight at least once that is consistent with the notes the array represents. If you add the results of different arrays together, what will you get? As the answer can get quite enormous, output it modulo $998\ 244\ 353$ .

Note that we only care about the minimum number of days when the notes with number $1$ are taken.

Input

Each test contains multiple test cases. The first line contains the number of test cases $T\ (1≤T≤10^4)$ .

Each test case consists of two lines.

The first line contains one integer $n\ (2\leq n\leq 5\times 10^5)$, the number of notes.

The second line contains $n$ integers $a_1,a_2,\dots,a_n\ (-1\leq a_i\leq 1)$, each number written on the note. The number is unknown if and only if $a_i=-1$.

It is guaranteed that $\sum n$ over all test cases in one test will not exceed $5\times 10^5$.

Output

For each test case, output $1$ integer: the sum of results modulo $998\ 244\ 353$ .

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

const ll MOD =  998244353;
const int N = 5e5+1;
const int M = 0;
vector<int> pow2(N); 
void pre()
{
    pow2[0] = 1;
    for(int i=1;i<N;i++)
    {
        pow2[i] = (pow2[i-1] * 2) % MOD;
    }
}
void solve()
{
    int n;
    cin >> n;
    vector<int> arr(n+1);
    int k = 0;
    for(int i=1;i<=n;i++)
    {
        cin >> arr[i];
        if(arr[i] == -1) k++;
    }
    // day 1 night 0
    // total 2^k cases
    int ans = 0;
    // 每种可能都会加上此天数，初始贡献为2^k
    if(arr[1] == 1) ans = pow2[k] % MOD; 
    // 否则钦定arr[1] = 1,此时产生贡献2^(k-1)
    if(arr[1] == -1) if(k-1>=0) ans = pow2[k-1] % MOD;
    // 当且仅当出现 0 1 这种情况时才会产生贡献
    for(int i=2;i<=n;i++)
    {
        if(arr[i] == 1)
        {
            if(arr[i-1] == 0)
            {
                // 无论何种情况都包括这一天，贡献了2^k
                ans = (ans + pow2[k]) % MOD; 
            }
            if(arr[i-1] == -1)
            {
                // 当且仅当arr[i-1] = 0时才可以贡献，固定arr[i-1]=0后的新贡献为2^(k-1)
                if(k-1>=0) ans = (ans + pow2[k-1]) % MOD; 
            }
        } 
        if(arr[i] == -1)
        {
            if(arr[i-1] == 0)
            {
                // 当且仅当 arr[i] = 1时才可以贡献，固定arr[i]=1后的新贡献为2^(k-1)
                if(k-1>=0) ans = (ans + pow2[k-1]) % MOD; 
            }
            if(arr[i-1] == -1)
            {	// 当且仅当 arr[i-1] = 0,arr[i] = 1时才可以产生贡献，固定这两个数后的新贡献为2^(k-2)
                if(k-2>=0) ans = (ans + pow2[k-2]) % MOD;
            }
        }
    }
    cout << ans << endl;
}