En permutasjon er en sekvens av lengde $n$ som består av heltall fra $1$ til $n$, der alle tallene forekommer nøyaktig én gang. For eksempel er $[1]$, $[3, 5, 2, 1, 4]$ og $[1, 3, 2]$ permutasjoner, mens $[2, 3, 2]$, $[4, 3, 1]$ og $[0]$ ikke er det.

Du får gitt en tabell $A_1, A_2, \dots, A_N$ som består av $N$ heltall. Hvert heltall er $0$ eller $1$. Finn antall permutasjoner $P$ av størrelse $N$ slik at følgende betingelser holder:

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

Fordi antallet slike permutasjoner kan være svært stort, skriv ut svaret modulo $998244353$.

Inndata

Den første linjen inneholder et heltall $N$ ($1 \le N \le 10^6$).

Den andre linjen inneholder $N$ mellomromseparerte heltall $A_i$ — elementene i tabellen. Det er garantert at $A_i \in \{0, 1\}$.

Utdata

Skriv ut én enkelt linje som inneholder antall permutasjoner som oppfyller betingelsene modulo $998244353$.

Eksempler

Eksempelinndata 1

2
1 0

Eksempelutdata 1

1

Eksempelinndata 2

1
0

Eksempelutdata 2

0

Eksempelinndata 3

7
1 1 0 1 0 1 0

Eksempelutdata 3

8