Una permutazione è una sequenza di lunghezza $n$ composta da interi da $1$ a $n$, in cui tutti i numeri compaiono esattamente una volta. Ad esempio, $[1]$, $[3, 5, 2, 1, 4]$ e $[1, 3, 2]$ sono permutazioni, mentre $[2, 3, 2]$, $[4, 3, 1]$ e $[0]$ non lo sono.
Ti viene dato un array $A_1, A_2, \dots, A_N$ composto da $N$ interi. Ogni intero è $0$ oppure $1$. Trova il numero di permutazioni $P$ di dimensione $N$ tali che valgano le seguenti condizioni:
- $P_1 < P_2 > P_3 < P_4 \dots$
- $A_{P_i} \equiv i \pmod 2$, per tutti gli ($1 \le i \le N$).
Poiché il numero di tali permutazioni può essere molto grande, stampa la risposta modulo $998244353$.
Input
La prima riga contiene un intero $N$ ($1 \le N \le 10^6$).
La seconda riga contiene $N$ interi separati da spazi $A_i$ — gli elementi dell'array. È garantito che $A_i \in \{0, 1\}$.
Output
Stampa una singola riga contenente il numero di permutazioni che soddisfano le condizioni modulo $998244353$.
Esempi
Input di esempio 1
2 1 0
Output di esempio 1
1
Input di esempio 2
1 0
Output di esempio 2
0
Input di esempio 3
7 1 1 0 1 0 1 0
Output di esempio 3
8