Umröðun er runa af lengd $n$ sem samanstendur af heiltölum frá $1$ til $n$, þar sem allar tölurnar koma fyrir nákvæmlega einu sinni. Til dæmis eru $[1]$, $[3, 5, 2, 1, 4]$ og $[1, 3, 2]$ umraðanir, en $[2, 3, 2]$, $[4, 3, 1]$ og $[0]$ eru það ekki.

Þér er gefið fylki $A_1, A_2, \dots, A_N$ sem samanstendur af $N$ heiltölum. Hver heiltala er $0$ eða $1$. Finndu fjölda umraðana $P$ af stærð $N$ þannig að eftirfarandi skilyrði gildi:

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

Þar sem fjöldi slíkra umraðana getur verið mjög mikill skaltu prenta svarið modulo $998244353$.

Inntak

Fyrsta línan inniheldur heiltölu $N$ ($1 \le N \le 10^6$).

Önnur línan inniheldur $N$ heiltölur $A_i$ aðskildar með bili — stök fylkisins. Það er tryggt að $A_i \in \{0, 1\}$.

Úttak

Prentaðu eina línu sem inniheldur fjölda umraðana sem uppfylla skilyrðin modulo $998244353$.

Dæmi

Dæmi um inntak 1

2
1 0

Dæmi um úttak 1

1

Dæmi um inntak 2

1
0

Dæmi um úttak 2

0

Dæmi um inntak 3

7
1 1 0 1 0 1 0

Dæmi um úttak 3

8