Eine Permutation ist eine Folge der Länge $n$, die aus ganzen Zahlen von $1$ bis $n$ besteht, in der alle Zahlen genau einmal vorkommen. Beispielsweise sind $[1]$, $[3, 5, 2, 1, 4]$ und $[1, 3, 2]$ Permutationen, während $[2, 3, 2]$, $[4, 3, 1]$ und $[0]$ keine sind.

Gegeben ist ein Array $A_1, A_2, \dots, A_N$, das aus $N$ ganzen Zahlen besteht. Jede ganze Zahl ist $0$ oder $1$. Bestimmen Sie die Anzahl der Permutationen $P$ der Größe $N$, sodass die folgenden Bedingungen erfüllt sind:

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

Da die Anzahl solcher Permutationen sehr groß sein kann, geben Sie die Antwort modulo $998244353$ aus.

Eingabe

Die erste Zeile enthält eine ganze Zahl $N$ ($1 \le N \le 10^6$).

Die zweite Zeile enthält $N$ durch Leerzeichen getrennte ganze Zahlen $A_i$ — die Elemente des Arrays. Es wird garantiert, dass $A_i \in \{0, 1\}$ gilt.

Ausgabe

Geben Sie eine einzige Zeile aus, die die Anzahl der Permutationen, welche die Bedingungen erfüllen, modulo $998244353$ enthält.

Beispiele

Beispieleingabe 1

2
1 0

Beispielausgabe 1

1

Beispieleingabe 2

1
0

Beispielausgabe 2

0

Beispieleingabe 3

7
1 1 0 1 0 1 0

Beispielausgabe 3

8