Permutacją nazywamy ciąg długości $n$ składający się z liczb całkowitych od $1$ do $n$, w którym wszystkie liczby występują dokładnie raz. Na przykład $[1]$, $[3, 5, 2, 1, 4]$ oraz $[1, 3, 2]$ są permutacjami, natomiast $[2, 3, 2]$, $[4, 3, 1]$ oraz $[0]$ nimi nie są.

Dana jest tablica $A_1, A_2, \dots, A_N$ składająca się z $N$ liczb całkowitych. Każda liczba całkowita to $0$ lub $1$. Znajdź liczbę permutacji $P$ rozmiaru $N$, dla których spełnione są następujące warunki:

• $P_1 < P_2 > P_3 < P_4 \dots$
• $A_{P_i} \equiv i \pmod 2$, dla wszystkich ($1 \le i \le N$).

Ponieważ liczba takich permutacji może być bardzo duża, wypisz odpowiedź modulo $998244353$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $N$ ($1 \le N \le 10^6$).

Drugi wiersz zawiera $N$ oddzielonych spacjami liczb całkowitych $A_i$ — elementy tablicy. Gwarantowane jest, że $A_i \in \{0, 1\}$.

Wyjście

Wypisz jeden wiersz zawierający liczbę permutacji spełniających warunki modulo $998244353$.

Przykłady

Przykładowe wejście 1

2
1 0

Przykładowe wyjście 1

1

Przykładowe wejście 2

1
0

Przykładowe wyjście 2

0

Przykładowe wejście 3

7
1 1 0 1 0 1 0

Przykładowe wyjście 3

8