分成四队

时间限制：2s
空间限制：1024MB

题目描述

有 $N$ 个人，第 $i$ 个人的力量为 $P_i$。把每个人分配到有标号的 A、B、C、D 四队之一，求同时满足以下条件的分配方案数：四队都非空；A 队力量和等于 B 队力量和；C 队力量和等于 D 队力量和。答案对 $998244353$ 取模。

输入格式

第一行一个整数 $N$，第二行 $N$ 个整数 $P_1,P_2,\ldots,P_N$。

输出格式

输出满足条件的方案数对 $998244353$ 取模后的结果。

样例输入 1

4
1 1 2 2

样例输出 1

8

样例输入 2

9
1 2 3 4 5 6 7 8 9

样例输出 2

0

数据范围

对于所有数据，$4\le N\le500$，$P_i\ge1$，且 $\sum P_i\le10^5$。