Косия и Махиру играют в игру с тремя массивами \(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\)).
Выходные данные
Выведите одно целое число — количество массивов \(c\), при которых выигрывает Косия, по модулю \(998\,244\,353\).
Примечание
В первом примере есть \(6\) массивов \(c\), при которых выигрывает Косия: \([1, 2, 3]\), \([1, 3, 2]\), \([2, 2, 3]\), \([2, 3, 2]\), \([3, 2, 3]\), \([3, 3, 2]\).
Во втором примере можно показать, что нет массивов \(c\), при которых выигрывает Косия.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
1 2 2
1 3 3
5
3 3 1 3 4
4 5 2 5 5
|
6
0
|