配点 : $600$ 点

問題文

$N$ 個の整数が与えられます。$i$ 個目の整数は $a_i$ です。 与えられたすべての整数を赤、緑、青の $3$ 色のいずれかで塗り、以下の条件を満たすようにする方法の個数を $998244353$ で割ったあまりを求めてください。

• 赤、緑、青で塗られた整数の総和をそれぞれ $R,G,B$ とする。三辺の長さがそれぞれ $R,G,B$ であるような正の面積の三角形が存在する。

制約

• $3 \leq N \leq 300$
• $1 \leq a_i \leq 300(1\leq i\leq N)$
• 入力はすべて整数である

入力

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

$N$

$a_1$

$:$

$a_N$

出力

与えられたすべての整数を赤、緑、青の $3$ 色のいずれかで塗り、条件を満たすようにする方法の個数を $998244353$ で割ったあまりを出力せよ。

4
1
1
1
2

18

三角形の三辺の長さがそれぞれ $1,2,2$ となるように整数を塗り分けるしかなく、そのような塗り分け方は $18$ 通り存在します。

6
1
3
2
3
5
2

150

20
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9
3
2
3
8
4

563038556