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

Вам дан массив $A_1, A_2, \dots, A_N$, состоящий из $N$ целых чисел. Каждое число равно $0$ или $1$. Найдите количество перестановок $P$ размера $N$, для которых выполняются следующие условия:

• $P_1 < P_2 > P_3 < P_4 \dots$
• $A_{P_i} \equiv i \pmod 2$ для всех ($1 \le i \le N$).

Так как количество таких перестановок может быть очень большим, выведите ответ по модулю $998244353$.

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

Первая строка содержит целое число $N$ ($1 \le N \le 10^6$).

Вторая строка содержит $N$ разделенных пробелами целых чисел $A_i$ — элементы массива. Гарантируется, что $A_i \in \{0, 1\}$.

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

Выведите одну строку, содержащую количество перестановок, удовлетворяющих условиям, по модулю $998244353$.

Примеры

Пример ввода 1

2
1 0

Пример вывода 1

1

Пример ввода 2

1
0

Пример вывода 2

0

Пример ввода 3

7
1 1 0 1 0 1 0

Пример вывода 3

8