004 - Red Black Balls

時間制限 2 秒 / メモリ制限 256 MB / 得点 200 / x 1 /


TLE
2sec
MLE
256MB
得点
200

問題

$N \ $個のボールがあり、$i \ (1 \leq i \leq N) \ $番目のボールには整数$ \ A_i \ $が書かれています。
これらのボールを青色または赤色の塗料で塗ります。塗り分け方は$ \ 2^N \ $通りありますが、青色で塗られたボールに書かれた整数の総和が赤色のボールに書かれた整数の総和と等しくなるような塗り分け方の総数を$ \ 998244353 \ $で割った余りを求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1 \ A_2 \ \ldots \ A_N$

出力

塗り方の総数を$ \ 998244353 \ $で割った余りを出力せよ。出力の末尾には改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

  • $2 \leq N \leq 200$
  • $0 \leq A_i \leq 200$
  • 入力は全て整数

入出力例

入力例1

6
0 1 3 4 1 5

出力例1

4
  • 青,青,赤,赤,青,青
  • 赤,青,赤,赤,青,青
  • 青,赤,青,青,赤,赤
  • 赤,赤,青,青,赤,赤

の$ \ 4 \ $通りです


入力例2

2
0 2

出力例2

0

条件を満たす塗り分け方は存在しません

入力例にはありませんが、$998244353 \ $で割った余りを出力することを忘れずに