一個排列是一個長度為 $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