Перестановкою називається послідовність довжини $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