Description

小A给你N个整数.第i个整数是叫ai。现在要你将这N个整数分别染上红、 绿、蓝三种颜色。

若将同色数字的和分别记为R,G,B

•R：所有被染上红色的数字的和 •G:所有被染上绿色的数字的和 •B:所有被染上蓝色的数字的和

试求使得R,G,B作为三边长可以构成三角形的涂色方案数量。

结果模 998244353。

Input Format

第1行输入一个整数N

接下来有N行，每行输入一个数字，分别代表耐a1--aN

Output Format

输出一个数，表示满足条件的涂色方案个数。（模998244353输出）

Sample

样例输入1

4
1
1
1
2

样例输出1

18

样例输入2

6
1
3
2
3
5
2

样例输出2

150

样例输入3

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

样例输出3

563038556

Hint

3 =< N <= 300

1 =< ai <= 300(1 < % < N)

•所有输入的值都是整数