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