Una permutación es una secuencia de longitud $n$ que consta de enteros del $1$ al $n$, en la que todos los números aparecen exactamente una vez. Por ejemplo, $[1]$, $[3, 5, 2, 1, 4]$ y $[1, 3, 2]$ son permutaciones, mientras que $[2, 3, 2]$, $[4, 3, 1]$ y $[0]$ no lo son.

Se te da un arreglo $A_1, A_2, \dots, A_N$ que consta de $N$ enteros. Cada entero es $0$ o $1$. Encuentra el número de permutaciones $P$ de tamaño $N$ tales que se cumplan las siguientes condiciones:

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

Como el número de tales permutaciones puede ser muy grande, imprime la respuesta módulo $998244353$.

Entrada

La primera línea contiene un entero $N$ ($1 \le N \le 10^6$).

La segunda línea contiene $N$ enteros separados por espacios $A_i$ — los elementos del arreglo. Se garantiza que $A_i \in \{0, 1\}$.

Salida

Imprime una sola línea que contenga el número de permutaciones que satisfacen las condiciones módulo $998244353$.

Ejemplos

Entrada de ejemplo 1

2
1 0

Salida de ejemplo 1

1

Entrada de ejemplo 2

1
0

Salida de ejemplo 2

0

Entrada de ejemplo 3

7
1 1 0 1 0 1 0

Salida de ejemplo 3

8