Steve 有一个排列$$$^{\text{*}}$$$ $$$p$$$ 和一个数组 $$$c$$$,长度均为 $$$n$$$。 Steve 希望对排列 $$$p$$$ 进行排序。
史蒂夫有无限量的彩色沙块,他利用它们发现了一种基于物理的方法来对数字数组进行排序,称为重力排序。也就是说,要对 $$$p$$$ 执行重力排序,Steve 将执行以下操作:
- 对于所有$$$i$$$,使得$$$1 \le i \le n$$$,将一个颜色为$$$c_i$$$的沙块放置在位置$$$(i, j)$$$,对于所有$$$j$$$,其中$$$1 \le j \le p_i$$$。这里,位置$$$(x, y)$$$表示从顶部算起第$$$x$$$行和从左边算起第$$$y$$$列中的单元格。
- 对阵列施加向下的重力,使所有沙块只要能落下就落下。
第三个测试用例的重力排序示例。 $$$p = [4, 2, 3, 1, 5]$$$, $$$c = [2, 1, 4, 1, 5]$$$ Alex 在执行重力排序后查看 Steve 的沙块,想知道有多少对数组 $$$(p',c')$$$(其中 $$$p'$$$ 是排列)会产生相同的沙子布局。请注意,原始数组 $$$(p, c)$$$ 将始终被计算在内。
请为 Alex 计算这个。由于这个数字可能很大,因此输出它对 $$$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$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组的长度。
每个测试用例的第二行包含 $$$n$$$ 不同 上面写着 整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$) — $$$p$$$ 的元素。
以下行包含 $$$n$$$ 整数 $$$c_1,c_2,\ldots,c_n$$$ ($$$1 \le c_i \le n$$$) — $$$c$$$ 的元素。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 Steve 可以开始使用的数组对的数量 $$$(p', c')$$$,以 $$$998\,244\,353$$$ 为模。
示例
输入复制
411155 3 4 1 21 1 1 1 154 2 3 1 52 1 4 1 54029 15 20 35 37 31 27 1 32 36 38 25 22 8 16 7 3 28 11 12 23 4 14 9 39 13 10 30 6 2 24 17 19 5 34 18 33 26 40 213 1 2 2 1 2 3 1 1 1 1 2 1 3 1 1 3 1 1 1 2 2 1 3 3 3 2 3 2 2 2 2 1 3 2 1 1 2 2 2
输出复制
1 120 1 143654893
注意
第二个测试用例如下所示。
第二个测试用例的重力排序。 可以证明$$$p$$$的排列会产生相同的结果,并且$$$c$$$必须等于$$$[1,1,1,1,1]$$$(因为所有沙子必须是相同的颜色),所以答案是$$$5! = 120$$$。
第三个测试用例如上面的语句所示。可以证明,没有其他数组$$$p$$$和$$$c$$$会产生相同的最终结果,所以答案是$$$1$$$。