【题目描述】
有n个小朋友排成一列，从左到右依次报给你n个数，每个小朋友报的数表示他自己以及相邻的小朋友中男生一共有几个。求n个小朋友性别的所有2^n种情况中，有多少种使得所有小朋友的话均成立。
【输入格式】
输入文件包含多组数据。第一行一个正整数T，表示有T组数据。每组数据的第一行为一个正整数n，然后一行是小朋友报给你的n个数。
【输出格式】
输出T行，每行一个整数表示方案数，对998244353取模。

Sample 1

Input

1
2
1 1

Output

2

【数据规模与限制】
10个测试点，内存限制：256MB，时限：1S
对于30%的数据,n<=15
对于40%的数据,n<=100
对于60%的数据,n<=1000
对于100%数据,3<=n<=300000,T<=10

【提示】
请读入char类型或者使用快读。
附赠快读模板：