MEX 正确子序列

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

对整数序列 $x_1,x_2,\ldots,x_k$，若对每个前缀都满足

$$\left|x_i-\operatorname{MEX}(x_1,x_2,\ldots,x_i)\right|\le 1,$$

则称它是 MEX 正确的。这里 $\operatorname{MEX}$ 是序列中没有出现的最小非负整数。

给定非负整数数组 $a$，求它有多少个非空 MEX 正确子序列。两个子序列只要选择的原数组下标不同，就视为不同。答案对 $998244353$ 取模。

输入格式

第一行包含整数 $t$，表示测试用例数。

每个测试用例的第一行包含整数 $n$，第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例输出一行一个整数，表示非空 MEX 正确子序列数模 $998244353$ 的结果。

样例输入 1

4
3
0 2 1
2
1 0
5
0 0 0 0 0
4
0 1 2 3

样例输出 1

4
2
31
7

数据范围

对于所有测试数据：

• $1\le t\le 10^5$；
• $1\le n\le 5\times10^5$；
• $0\le a_i\le n$；
• 所有测试用例的 $\sum n\le 5\times10^5$。

子任务编号	分值	特殊限制
1	30	每组 $n\le 18$，且 $a_i\le 12$
2		每组 $n\le 1000$，且 $a_i\le 12$
3	40	无特殊限制

每个测试点独立计分；同一子任务内各测试点等分。