聚会上有 $$$n$$$ 人。第 $$$i$$$ 人拥有一定的幸福感 $$$a_i$$$。
每个人都有某种性格,可以用二进制整数 $$$b$$$ 表示。如果$$$b = 0$$$,这意味着如果这个人把这个故事讲给一个严格来说比他们不那么幸福的人,他的幸福感就会增加。如果$$$b = 1$$$,这意味着如果这个人把这个故事讲给比他们更幸福的人,他的幸福感就会增加。
让我们将发言顺序定义为人们从左到右的顺序。现在发生以下过程。我们从左到右。当前的人向除了他自己之外的所有人讲述这个故事。请注意,在这种情况发生时,所有幸福值都保持不变。在这个人完成之后,他会根据他的性格来计算当前幸福感严格低于/高于他的人的数量,并且他的幸福感会增加该值。请注意,只有当前人的幸福值会增加。
作为聚会的组织者,您不希望任何人悲伤地离开。因此,您想要计算发言顺序的数量,以便在过程结束时所有 $$$n$$$ 人都拥有平等的幸福感。
如果两个发言顺序中至少存在一个人的位置不同,则认为两个发言顺序不同。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 人数。
第二行包含一系列 $$$n$$$ 整数 $$$a_1,a_2,...,a_n$$$ ($$$1 \leq a_i \leq 2n$$$) — 幸福值。
第三行包含一系列 $$$n$$$ 二进制数 $$$b_1,b_2,...,b_n$$$ ($$$b_i \in \{0,1\}$$$) — 人格类型。
输出
输出不同有效发言顺序的数量。由于这个数字可能很大,因此输出它对 $$$998244353$$$ 取模。
示例
输入 #1
4 1 2 4 4 1 1 0 0
输出 #1
2
输入 #2
4 3 4 3 1 0 1 0 0
输出 #2
0
输入 #3
21 1 2 19 19 19 19 19 19 19 19 19 21 21 21 21 21 21 21 21 21 21 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
输出 #3
49439766
注意
这是第一个示例的说明。一种有效的发言顺序是 $$$[2,1,4,3]$$$(这里,我们写下了每个人的索引)。每一步都显示当前的幸福值和结果。
步骤$$$1$$$:$$$[1,2,4,4]$$$ $$$\rightarrow$$$ 人$$$2$$$向其他人讲述故事。由于他的性格类型为 $$$1$$$,因此他的幸福感增加了 $$$2$$$,因为 $$$3$$$ 和 $$$4$$$ 的人拥有严格意义上更大的幸福感。
步骤$$$2$$$:$$$[1,4,4,4]$$$ $$$\rightarrow$$$ 人$$$1$$$向其他人讲述故事。由于他的性格类型是$$$1$$$,因此他的幸福感增加了$$$3$$$,因为$$$2$$$、$$$3$$$ 和$$$4$$$ 的幸福感更高。
步骤$$$3$$$:$$$[4,4,4,4]$$$ $$$\rightarrow$$$ 人$$$4$$$向其他人讲述故事。由于他的性格类型为$$$0$$$,因此他的幸福感增加了$$$0$$$,因为没有人的幸福感严格地低于$$$0$$$。
步骤$$$4$$$:$$$[4,4,4,4]$$$ $$$\rightarrow$$$ 人$$$3$$$向其他人讲述故事。由于他的性格类型为$$$0$$$,因此他的幸福感增加了$$$0$$$,因为没有人的幸福感严格地低于$$$0$$$。
最终,每个人都拥有平等的幸福。
请注意,$$$[2,1,3,4]$$$ 也是此示例的有效答案。
可以证明第二个示例没有有效的排序。