E. Сортировка песка в Mycraft
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Стива есть перестановка$$$^{\text{∗}}$$$ $$$p$$$ и массив $$$c$$$, оба — длины $$$n$$$. Стив хочет отсортировать перестановку $$$p$$$.

У Стива есть бесконечное количество цветных песчаных блоков, и с их помощью он обнаружил способ сортировки массива чисел, основанный на физике, называемый гравитационной сортировкой. А именно, чтобы выполнить гравитационную сортировку на $$$p$$$, Стив будет делать следующее:

  • Для всех $$$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]$$$

Алекс смотрит на песчаные блоки Стива после выполнения гравитационной сортировки и задается вопросом, сколько пар массивов $$$(p',c')$$$, где $$$p'$$$ является перестановкой, привели бы к такому же расположению песка. Обратите внимание, что оригинальная пара массивов $$$(p, c)$$$ всегда будет учитываться.

Пожалуйста, помогите Алекс вычислить это. Поскольку это число может быть огромным, выведите его по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Перестановка длины $$$n$$$ — это массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите количество пар массивов $$$(p', c')$$$, с которых Стив мог начать, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4
1
1
1
5
5 3 4 1 2
1 1 1 1 1
5
4 2 3 1 5
2 1 4 1 5
40
29 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 21
3 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$$$.