题目描述

有 $N$ 个橘子，编号为 $1$ 到 $N$。第 $i$ 个橘子的重量为 $W_i$。高桥君和青木君将按照以下方式分橘子：

• 选择一个 $(1,2,\cdots,N)$ 的排列 $(p_1,\ p_2,\ \cdots,\ p_N)$。

• 对于 $i=1,2,\cdots,N$，依次进行以下操作：

  • 如果高桥君已经拿到的橘子总重量小于等于青木君已经拿到的橘子总重量，则高桥君拿橘子 $p_i$。否则，青木君拿橘子 $p_i$。

请你求出有多少种排列 $p$，使得最终两人拿到的橘子总重量相等。答案对 $998244353$ 取模。

输入格式

输入从标准输入读入，格式如下：

$N$ $W_1$ $W_2$ $\cdots$ $W_N$

输出格式

输出答案。

样例 1

输入

3
1 1 2

输出

4

样例 2

输入

4
1 2 3 8

输出

0

样例 3

输入

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

输出

373835282

说明/提示

限制条件

• $2 \leq N \leq 100$
• $1 \leq W_i \leq 100$
• 输入的所有数均为整数

样例解释 1

满足条件的排列 $p$ 有 $(1,3,2),(2,3,1),(3,1,2),(3,2,1)$ 共 $4$ 种。例如，当 $p=(3,2,1)$ 时，过程如下：

• $i=1$：高桥君已拿橘子总重量为 $0$，青木君已拿橘子总重量为 $0$。高桥君拿橘子 $p_i=3$。
• $i=2$：高桥君已拿橘子总重量为 $2$，青木君已拿橘子总重量为 $0$。青木君拿橘子 $p_i=2$。
• $i=3$：高桥君已拿橘子总重量为 $2$，青木君已拿橘子总重量为 $1$。青木君拿橘子 $p_i=1$。

因此 $p=(3,2,1)$ 满足条件。

由 ChatGPT 4.1 翻译