D. Косия и игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Косия и Махиру играют в игру с тремя массивами $$$a$$$, $$$b$$$ и $$$c$$$ длины $$$n$$$. Каждый элемент $$$a$$$, $$$b$$$ и $$$c$$$ — целое число от $$$1$$$ до $$$n$$$ включительно.

Игра состоит из $$$n$$$ раундов. В $$$i$$$-м раунде они делают следующие ходы:

  • Пусть $$$S$$$ — мультимножество $$$\{a_i, b_i, c_i\}$$$.
  • Косия удаляет один из элементов $$$S$$$ по своему выбору.
  • Затем Махиру выбирает одно из двух оставшихся в $$$S$$$ чисел.

Пусть $$$d_i$$$ — число, выбранное Махиру в $$$i$$$-м раунде. Если $$$d$$$ является перестановкой$$$^\dagger$$$, Косия выигрывает. Иначе выигрывает Махиру.

Сейчас выбраны только массивы $$$a$$$ и $$$b$$$. Являясь ярым поклонником Косии, вы хотите выбрать массив $$$c$$$ так, чтобы Косия выиграла. Вычислите количество таких $$$c$$$ по модулю $$$998\,244\,353$$$.

Обратите внимание, что Косия и Махиру играют оптимально.

$$$^\dagger$$$ Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq {10}^5$$$) — размеры массивов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq n$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$${10}^5$$$.

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

Выведите одно целое число — количество массивов $$$c$$$, при которых выигрывает Косия, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
2
3
1 2 2
1 3 3
5
3 3 1 3 4
4 5 2 5 5
Выходные данные
6
0
Примечание

В первом примере есть $$$6$$$ массивов $$$c$$$, при которых выигрывает Косия: $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 2, 3]$$$, $$$[2, 3, 2]$$$, $$$[3, 2, 3]$$$, $$$[3, 3, 2]$$$.

Во втором примере можно показать, что нет массивов $$$c$$$, при которых выигрывает Косия.