凯文喜欢逻辑谜题。
他和 $$$n$$$ 排成一排的同学玩游戏。左边第 $$$i$$$ 人说他们左边有 $$$a_i$$$ 骗子(不包括他们自己)。
每个同学要么是诚实的,要么是说谎的,但限制是不能有两个说谎的人并排站立。诚实的同学总是说实话。说谎者可以说真话,也可以说谎话,这意味着他们的陈述被认为是不可靠的。
Kevin 想要确定以 $$$998\,244\,353$$$ 为模的不同可能游戏配置的数量。如果至少一名同学在一种配置中是诚实的,而在另一种配置中是骗子,则两种配置被认为是不同的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n \leq 2 \cdot 10^5$$$) — 同学的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i \leq n$$$) — 他们声称的第 $$$i$$$ 人左边的骗子数量。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 不同游戏配置的数量以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
8 3 0 1 2 5 0 0 0 0 0 5 0 0 1 1 2 5 0 1 2 3 4 5 0 0 1 1 1 5 5 1 5 2 5 1 0 4 2 3 1 1
输出 #1
1 2 3 0 4 1 2 0
注意
我们将使用 $$$\color{red}{\text{red}}$$$ 来标记说谎者,使用 $$$\color{blue}{\text{blue}}$$$ 来标记诚实的人。
在第一个测试用例中,唯一可能的方法是 $$$(\color{red}{0},\color{blue}{1},\color{red}{2})$$$。
在第二个测试用例中,两种可能的方式是 $$$(\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0})$$$ 和 $$$(\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{blue}{0},\color{red}{0})$$$。
在第三个测试用例中,三种可能的方式是 $$$(\color{blue}{0},\color{blue}{0},\color{red}{1},\color{blue}{1},\color{red}{2})$$$, $$$(\color{blue}{0},\color{red}{0},\color{blue}{1},\color{red}{1},\color{blue}{2})$$$, $$$(\颜色{蓝色}{0}、\颜色{红色}{0}、\颜色{蓝色}{1}、\颜色{蓝色}{1}、\颜色{红色}{2})$$$。