分数: 600 点
问题陈述
有 N 人数 1, \dots ,N。的 实力 人的 人的 i is P_i.
每个人被分配到其中一个团队 A,B,C,D 组成四队。有 4^N 组建团队的方式;其中,找到数字,模 998244353,满足以下所有条件的地层。
- 各队 A,B,C,D 至少有一个人。
- 团队成员的力量总和 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
以下八个队形满足条件。
| 人 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