Permutaatio on pituuden $n$ lukujono, joka koostuu kokonaisluvuista väliltä $1$ – $n$ ja jossa jokainen luku esiintyy täsmälleen kerran. Esimerkiksi $[1]$, $[3, 5, 2, 1, 4]$ ja $[1, 3, 2]$ ovat permutaatioita, kun taas $[2, 3, 2]$, $[4, 3, 1]$ ja $[0]$ eivät ole.

Sinulle annetaan taulukko $A_1, A_2, \dots, A_N$, joka koostuu $N$ kokonaisluvusta. Jokainen kokonaisluku on $0$ tai $1$. Etsi sellaisten koon $N$ permutaatioiden $P$ lukumäärä, joille seuraavat ehdot pätevät:

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

Koska tällaisten permutaatioiden lukumäärä voi olla hyvin suuri, tulosta vastaus modulo $998244353$.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $N$ ($1 \le N \le 10^6$).

Toinen rivi sisältää $N$ välilyönnein eroteltua kokonaislukua $A_i$ — taulukon alkiot. On taattu, että $A_i \in \{0, 1\}$.

Tuloste

Tulosta yksi rivi, joka sisältää ehdot täyttävien permutaatioiden lukumäärän modulo $998244353$.

Esimerkit

Esimerkkisyöte 1

2
1 0

Esimerkkituloste 1

1

Esimerkkisyöte 2

1
0

Esimerkkituloste 2

0

Esimerkkisyöte 3

7
1 1 0 1 0 1 0

Esimerkkituloste 3

8