順列とは、$1$ から $n$ までの整数からなる長さ $n$ の数列であり、すべての数がちょうど 1 回ずつ現れるものです。例えば、$[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$ で割った余りを出力してください。

入力

1 行目には整数 $N$ ($1 \le N \le 10^6$) が与えられます。

2 行目には配列の要素を表す $N$ 個の空白区切りの整数 $A_i$ が与えられます。$A_i \in \{0, 1\}$ であることが保証されます。

出力

条件を満たす順列の個数を $998244353$ で割った余りを 1 行で出力してください。

入出力例

入力例 1

2
1 0

出力例 1

1

入力例 2

1
0

出力例 2

0

入力例 3

7
1 1 0 1 0 1 0

出力例 3

8