На вечеринке есть $$$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$$$.
4 1 2 4 4 1 1 0 0
2
4 3 4 3 1 0 1 0 0
0
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
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$$$, так как ни у кого нет строго меньшего уровня счастья.
Шаг $$$4$$$: $$$[4,4,4,4]$$$ $$$\rightarrow$$$ Человек $$$3$$$ рассказывает историю остальным. Так как его тип личности равен $$$0$$$, его счастье увеличится на $$$0$$$, так как ни у кого нет строго меньшего уровня счастья.
В итоге, у всех одинаковый уровень счастья.
Заметьте, что $$$[2,1,3,4]$$$ также является корректным порядком для примера.
Можно показать, что не существует корректных порядков во втором примере.
