Необычная сортировка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Для этого Магане может один раз выбрать произвольный набор различных позиций в массиве и заменить элементы на этих позициях на противоположные, то есть умножить их на $$$-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$$$).

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

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

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
17$$$n \leqslant 3$$$полная
212$$$n \leqslant 10$$$1полная
39 $$$1 \leqslant a_i \leqslant n$$$, все элементы массива различны полная
419 $$$1 \leqslant a_i$$$, все элементы массива различны 3полная
513существует $$$i$$$, при котором $$$a_i = 0$$$полная
618 каждое число либо встречается в массиве дважды, либо не встречается вообще полная
722нет1 – 6первая ошибка

Примеры

Входные данные
4
5 3 3 2
Выходные данные
2
Входные данные
5
4 3 2 3 1
Выходные данные
0