Задача №114773. Необычная сортировка

Магане любит брать обычные вещи и выворачивать их смысл наизнанку. В этот раз ей попался совершенно обычный массив целых чисел, и чтобы избавиться от скуки, она хочет сделать его отсортированным по неубыванию.

Для этого Магане может один раз выбрать произвольный набор различных позиций в массиве и заменить элементы на этих позициях на противоположные, то есть умножить их на \(-1\). Например, чтобы сделать массив \([-4, 4, 1, 3, -10]\) отсортированным, она может умножить на \(-1\) числа на позициях \(2\) и \(5\), и получить массив \([-4, -4, 1, 3, 10]\).

К сожалению, надолго ее такое занятие не увлечет, поэтому Магане решила посчитать количество способов отсортировать массив по неубыванию указанным образом. Два способа считаются различными, если различаются выбранные ей наборы позиций.

Помогите ей с этой задачей! Поскольку итоговое количество способов может быть слишком большим, найдите ответ по модулю \(998244353\).

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

В первой строке ввода записано целое число \(n\) — количество элементов в массиве (\(1 \leqslant n \leqslant 10^6\)).

Во второй строке через пробел перечислены \(n\) целых чисел \(a_1\), \(a_2\), ..., \(a_n\) — элементы массива (\(-10^9 \leqslant a_i \leqslant 10^9\)).

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

Выведите одно число — количество способов отсортировать массив указанным образом (по модулю \(998244353\)).

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
1 7 \(n \leqslant 3\) полная
2 12 \(n \leqslant 10\) 1 полная
3 9 \(1 \leqslant a_i \leqslant n\), все элементы массива различны полная
4 19 \(1 \leqslant a_i\), все элементы массива различны 3 полная
5 13 существует \(i\), при котором \(a_i = 0\) полная
6 18 каждое число либо встречается в массиве дважды, либо не встречается вообще полная
7 22 нет 1 – 6 первая ошибка

Примеры
Входные данные
4
5 3 3 2
Выходные данные
2
Входные данные
5
4 3 2 3 1
Выходные данные
0
Сдать: для сдачи задач необходимо войти в систему