Alice 有一个大小为 $$$n \times n$$$ 的网格。最初,所有细胞都是白色的。 Alice 想要将一些单元格染成黑色以满足某些属性。
设 $$$(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)$$$ 为黑色单元格。给定一个大小为 $$$n$$$ 的数组 $$$a$$$。必须满足以下条件:
- 对于每一行 $$$k$$$ ($$$1 \le k \le n$$$),恰好存在 $$$a_k$$$ 索引 $$$i$$$ ($$$1 \le i \le m$$$) 使得 $$$x_i = k$$$。不太正式,$$$k$$$ 行中应该有 $$$a_k$$$ 黑色单元格。
- 对于每个 $$$k$$$ ($$$1 \le k \le n$$$),存在一个索引 $$$i$$$ 使得 $$$\max(x_i, y_i) = k$$$。
- 对于每个 $$$k$$$ ($$$1 \le k \le n$$$),存在一个索引 $$$i$$$ 使得 $$$\max(x_i, n + 1 - y_i) = k$$$。
例如,当 $$$a = [2, 2, 1, 0, 0]$$$ 时,一组可能的黑色单元格为 $$$\{(1, 1), (2, 2), (3, 3), (2, 4), (1, 5)\}$$$。这对应于以下网格:
5×5 网格,具有指定的黑色单元格。 计算可能的网格数。如果某个网格中某个单元格的颜色为黑色,而另一个网格中的单元格为白色,则 $$$2$$$ 网格被认为是不同的。由于答案可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 — $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$)
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一行包含一个整数:有效网格的数量以 $$$998\,244\,353$$$ 为模。
示例
输入复制
552 2 1 0 022 021 143 1 0 040 0 0 0
输出复制
11020
注意
在第一个测试用例中,唯一有效的网格是语句中的网格。
在第二个测试用例中,唯一有效的网格由黑色单元格 $$$\{(1, 1), (1, 2)\}$$$ 描述。
在第三个测试用例中,没有有效的网格。