問題文

Shirotsume は長さ $N$ の数列 $A = [A_1, A_2, \dots A_N]$ を持っています。数列 $A$ の値は全て $0$ または $1$ です。

数列 $A$ に対して、以下の操作を考えます。

操作:操作を行う前の数列 $A$ の長さを $M$ とする。数列 $A$ を数列 $A' = [(A_1\ \oplus\ A_2), (A_2\ \oplus\ A_3), (A_3\ \oplus\ A_4), ... (A_{M - 1}\ \oplus\ A_M)]$ に置き換える。

ただし、$a\ \oplus\ b$ は $a$ と $b$ の排他的論理和(XOR)を表します。

操作を $1$ 度行うと、数列は長さが $1$ 短くなります。数列 $A$ に操作を $N - 1$ 回繰り返し適用すると、$A$ は長さ $1$ の数列 $[0]$ または $[1]$ になります。

Shirotsume は長さが $N$ である数列 $A$ を一部隠して、長さ $N$ の数列 $B$ としてあなたに教えます。

数列 $B$ は $-1, 0, 1$ の値のみからなり、$1 ≤ i ≤ N$ について、$B_i = 0$ または$B_i = 1$ ならば $A_i = B_i$、$B_i = -1$ なら$A_i$ の値が隠されていることを表します。

$A$ の要素のうち隠されている要素の個数を $P$ とすると、$A$ としてありえる数列は $2^P$ 通りありますが、そのうち操作を $N - 1$ 回行った後 $A = [1]$ になるものは何通りありますか？ $998244353$ で割ったあまりを求めてください。

制約

• 入力は全て整数
• $2 \leq N \leq 2 \times 10^5$
• $B_i$ $(1 \leq i \leq N)$ の値は $-1, 0, 1$ のいずれか

入力

$N$
$B_1$ $B_2$ $B_3$ $...$ $B_N$

出力

操作を $N - 1$ 回行った結果 $A = [1]$ になるものの個数を $998244353$ で割ったあまりを出力せよ。

最後に改行すること。

サンプル

3
-1 -1 1

2

5
0 0 1 0 0

0

7
-1 0 1 0 1 1 -1

2