题目描述

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

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

输入格式

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

$N$ $a_1$ $:$ $a_N$

输出格式

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

题目大意

• 给你给 $N$ 个整数，第 $i$ 个为 $a_i$。
• 你需要给每个整数染上 R,G,B 三种颜色之一, 记三种颜色的整数的和分别为 $S_R,S_G,S_B$，并使得以 $S_R,S_B,S_G$ 为边能构成三角形。
• 求这样的染色方案数，对 $998244353$ 取模。

4
1
1
1
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

提示

制約

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

Sample Explanation 1

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