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 < P_2 > P_3 < P_4 \dots$
• $A_{P_i} \equiv i \pmod 2$, for all ($1 \le i \le 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 \le N \le 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

Sample Input 1

2
1 0

Sample Output 1

1

Sample Input 2

1
0

Sample Output 2

0

Sample Input 3

7
1 1 0 1 0 1 0

Sample Output 3

8