Problem Description

Given \( N \) integers, the \( i \)-th integer is \( a_i \). You are to paint all given integers either red, green, or blue, and find the number of ways to do so, modulo \( 998244353 \), such that the following condition is satisfied:

• Let \( R \), \( G \), and \( B \) be the sums of the integers painted red, green, and blue, respectively. There exists a triangle with positive area whose sides have lengths \( R \), \( G \), and \( B \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( a_1 \) \( : \) \( a_N \)

Output Format

Output the number of ways to paint all given integers either red, green, or blue such that the condition is satisfied, modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

4
1
1
1
2

Sample Output #1

18

Sample Input #2

6
1
3
2
3
5
2

Sample Output #2

150

Sample Input #3

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

Sample Output #3

563038556

Notes/Hints

Constraints

• \( 3 \leq N \leq 300 \)
• \( 1 \leq a_i \leq 300 \) for \( 1 \leq i \leq N \)
• All inputs are integers.

Sample Explanation 1

The only way to partition the integers such that the sides of the triangle are \( 1, 2, 2 \) respectively, and there are \( 18 \) such ways to do so.

见题面 Input 部分

见题面 Output 部分