F. Binary Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation is a sequence of length $$$n$$$ consisting of integers from $$$1$$$ to $$$n$$$, in which all the numbers occur exactly once. For example, $$$[1]$$$, $$$[3,5,2,1,4]$$$, and $$$[1,3,2]$$$ are permutations, whereas $$$[2,3,2]$$$, $$$[4,3,1]$$$, and $$$[0]$$$ are not.

You are given an array $$$A_1, A_2, \dots, A_N$$$ consisting of $$$N$$$ integers. Each integer is $$$0$$$ or $$$1$$$. Find the number of permutations $$$P$$$ of size $$$N$$$ such that the following conditions hold:

  • $$$P_1 \lt P_2 \gt P_3 \lt P_4 \dots$$$
  • $$$A_{P_i} \equiv i \pmod{2}$$$, for all ($$$1 \leq i \leq N$$$).

Because the number of such permutations can be very large, print the answer modulo $$$998244353$$$.

Input

The first line contains an integer $$$N \ (1 \leq N \leq 10^6)$$$.

The second line contains $$$N$$$ space separated integers $$$A_i$$$ - the elements of the array. It's guaranteed that $$$A_i \in \{0, 1\}$$$.

Output

Output a single line containing the number of permutations satisfying the conditions modulo $$$998244353$$$.

Examples
Input
2
1 0
Output
1
Input
1
0
Output
0
Input
7
1 1 0 1 0 1 0
Output
8