/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
1, \dots ,N の番号がついた N 人の人がいます。人 i の強さは P_i です。
各人を A,B,C,D のいずれかのチームに割り当てることで、4 つのチームにチーム分けをします。チーム分けの方法は 4^N 通りありますが、このうち以下の条件を全て満たすチーム分けの個数を 998244353 で割った余りを求めて下さい。
- A,B,C,D のどのチームにも 1 人以上所属する。
- チーム A に所属する人の強さの和とチーム B に所属する人の強さの和が等しい。
- チーム C に所属する人の強さの和とチーム D に所属する人の強さの和が等しい。
制約
- 4 \le N \le 500
- 1 \le P_i
- \sum_{1 \le i \le N} P_i \le 10^5
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \ldots P_N
出力
問題文中の条件を満たすチーム分けの個数を 998244353 で割った余りを出力せよ。
入力例 1
4 1 1 2 2
出力例 1
8
以下の 8 通りのチーム分けが条件を満たします。
| 人 1 | 人 2 | 人 3 | 人 4 | |
|---|---|---|---|---|
| チーム分け 1 | A | B | C | D |
| チーム分け 2 | B | A | C | D |
| チーム分け 3 | A | B | D | C |
| チーム分け 4 | B | A | D | C |
| チーム分け 5 | C | D | A | B |
| チーム分け 6 | C | D | B | A |
| チーム分け 7 | D | C | A | B |
| チーム分け 8 | D | C | B | A |
入力例 2
9 1 2 3 4 5 6 7 8 9
出力例 2
0
条件を満たすチーム分けが存在しません。
入力例 3
24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
出力例 3
289359125
Score : 600 points
Problem Statement
There are N people numbered 1, \dots ,N. The strength of person i is P_i.
Each person is assigned to one of the teams A,B,C,D to form four teams. There are 4^N ways to form teams; among these, find the number, modulo 998244353, of formations that satisfy all of the following conditions.
- Each of the teams A,B,C,D has at least one person.
- The sum of the strengths of the people in team A equals the sum of the strengths of the people in team B.
- The sum of the strengths of the people in team C equals the sum of the strengths of the people in team D.
Constraints
- 4 \le N \le 500
- 1 \le P_i
- \sum_{1 \le i \le N} P_i \le 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
Output the number, modulo 998244353, of formations that satisfy the conditions in the problem statement.
Sample Input 1
4 1 1 2 2
Sample Output 1
8
The following eight team formations satisfy the conditions.
| Person 1 | Person 2 | Person 3 | Person 4 | |
|---|---|---|---|---|
| Formation 1 | A | B | C | D |
| Formation 2 | B | A | C | D |
| Formation 3 | A | B | D | C |
| Formation 4 | B | A | D | C |
| Formation 5 | C | D | A | B |
| Formation 6 | C | D | B | A |
| Formation 7 | D | C | A | B |
| Formation 8 | D | C | B | A |
Sample Input 2
9 1 2 3 4 5 6 7 8 9
Sample Output 2
0
No formations satisfy the conditions.
Sample Input 3
24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Sample Output 3
289359125