题目描述

有 \(n\) 个小朋友排成一列，从左到右依次报给你 \(n\) 个数，每个小朋友报的数表示他自己以及相邻的小朋友中男生一共有几个。求 \(n\) 个小朋友性别的所有 \(2^n\) 种情况中，有多少种使得所有小朋友的话均成立。

格式

输入格式

输入文件包含多组数据。第一行一个正整数 \(T\)，表示有 \(T\) 组数据。每组数据的第一行为一个正整数 \(n\)，然后一行是小朋友报给你的 \(n\) 个数。

输出格式

输出 \(T\) 行，每行一个整数表示方案数，对 \(998244353\) 取模。

样例1

样例输入1

1
2
1 1

样例输出1

2

提示

请读入 \(\textbf{char}\) 类型或者使用快读。
附赠快读模板：

int read(){
    int r=0;char ch;
    do ch=getchar(); while (!isdigit(ch));
    do r=r*10+ch-48,ch=getchar(); while(isdigit(ch));
    return r;
}

限制

对于 \(30\%\) 的数据,\(n<=15\)
对于 \(40\%\) 的数据,\(n<=100\)
对于 \(60\%\) 的数据,\(n<=1000\)
对于 \(100\%\) 数据,\(3<=n<=300000,T<=10\)