En permutation är en talföljd av längd $n$ som består av heltal från $1$ till $n$, där alla tal förekommer exakt en gång. Till exempel är $[1]$, $[3, 5, 2, 1, 4]$ och $[1, 3, 2]$ permutationer, medan $[2, 3, 2]$, $[4, 3, 1]$ och $[0]$ inte är det.

Du får en array $A_1, A_2, \dots, A_N$ som består av $N$ heltal. Varje heltal är $0$ eller $1$. Hitta antalet permutationer $P$ av storlek $N$ sådana att följande villkor gäller:

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

Eftersom antalet sådana permutationer kan vara mycket stort, skriv ut svaret modulo $998244353$.

Indata

Den första raden innehåller ett heltal $N$ ($1 \le N \le 10^6$).

Den andra raden innehåller $N$ blankstegsavgränsade heltal $A_i$ — elementen i arrayen. Det garanteras att $A_i \in \{0, 1\}$.

Utdata

Skriv ut en enda rad som innehåller antalet permutationer som uppfyller villkoren modulo $998244353$.

Exempel

Exempelindata 1

2
1 0

Exempelutdata 1

1

Exempelindata 2

1
0

Exempelutdata 2

0

Exempelindata 3

7
1 1 0 1 0 1 0

Exempelutdata 3

8