对于大小为 $$$m \ge 3$$$ 的排列$$$^{\text{∗}}$$$ $$$q$$$,将 $$$f(q)$$$ 定义为大小为 $$$m - 2$$$ 的序列 $$$b$$$,使得 $$$b_i = \operatorname{med}(q_i, q_{i + 1}, q_{i + 2})$$$ 对于所有 $$$1 \le i \le m - 2$$$。这里,$$$\operatorname{med}(x, y, z)$$$表示$$$\{x, y, z\}$$$中第二小的元素。
给你一个大小为$$$n$$$的数组$$$a$$$,其中一些元素可能是$$$0$$$。保证 $$$a$$$ 包含值 $$$1$$$ 和 $$$n$$$ (即存在索引 $$$i, j$$$ 使得 $$$a_i = 1$$$ 和 $$$a_j = n$$$)。
求满足以下条件的大小为 $$$n$$$ 的排列 $$$p$$$ 的数量:
- $$$p$$$ 与 $$$a$$$ 一致:对于所有 $$$1 \le i \le n$$$,如果 $$$a_i \neq 0$$$,则 $$$p_i = a_i$$$。
- $$$f(p)$$$ 的所有元素都是 不同.
由于答案可能很大,请打印 $$$998\,244\,353$$$ 的模。
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 数组的大小。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$)。
保证 $$$a$$$ 的所有非零元素都是成对不同的。还保证 $$$a$$$ 包含值 $$$1$$$ 和 $$$n$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 满足条件的排列 $$$p$$$ 的数量,以 $$$998\,244\,353$$$ 为模。
示例
输入复制
531 3 250 5 4 1 070 0 1 0 0 7 0101 10 0 0 0 0 0 0 0 0150 0 10 0 0 15 0 0 6 7 0 1 0 0 3
输出复制
101014
注意
在第一个示例中,唯一与输入一致的排列是 $$$p = [1, 3, 2]$$$。我们有 $$$f(p) = [2]$$$,因为 $$$\operatorname{med}(1, 3, 2) = 2$$$。 $$$f(p)$$$ 的元素是不同的,因此这种排列是有效的。答案是$$$1$$$。
在第二个示例中,有两个与输入一致的排列:$$$p = [3, 5, 4, 1, 2]$$$ 和 $$$p = [2, 5, 4, 1, 3]$$$。
- 对于 $$$p = [3, 5, 4, 1, 2]$$$,$$$f(p) = [4, 4, 2]$$$。
- 对于 $$$p = [2, 5, 4, 1, 3]$$$,$$$f(p) = [4, 4, 3]$$$。