一个排列是一个长度为 $n$ 的序列，由 $1$ 到 $n$ 的整数组成，其中所有数字恰好出现一次。例如，$[1]$、$[3, 5, 2, 1, 4]$ 和 $[1, 3, 2]$ 是排列，而 $[2, 3, 2]$、$[4, 3, 1]$ 和 $[0]$ 不是。

给你一个由 $N$ 个整数组成的数组 $A_1, A_2, \dots, A_N$。每个整数为 $0$ 或 $1$。求满足以下条件的长度为 $N$ 的排列 $P$ 的数量：

• $P_1 < P_2 > P_3 < P_4 \dots$
• 对于所有 $1 \le i \le N$，满足 $A_{P_i} \equiv i \pmod 2$。

由于此类排列的数量可能非常大，请将答案模 $998244353$ 后输出。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^6$)。

第二行包含 $N$ 个空格分隔的整数 $A_i$ —— 数组的元素。保证 $A_i \in \{0, 1\}$。

输出格式

输出单行，包含满足条件的排列数量模 $998244353$ 的结果。

样例

输入样例 1

2
1 0

输出样例 1

1

输入样例 2

1
0

输出样例 2

0

输入样例 3

7
1 1 0 1 0 1 0

输出样例 3

8