分数: 800 点
问题陈述
我们有 N 橙子,已编号 1 通过 N。 橙子的重量 i is W_i。 高桥和青木将分享这些橙子如下。
-
选择一个排列 (p_1, p_2, \cdots, p_N) of (1,2,\cdots,N).
-
对于每个 i = 1, 2, \cdots, N 按照此顺序,执行以下操作。
- 如果高桥拿走的橙子总重量不大于青木拿走的橙子的总重量,则高桥拿走橙子 p_i。 否则,青木拿下橙色 p_i.
求排列数 p 模数 998244353 使得高桥拿走的橙子的总重量等于青木拿走的橙子的总重量。
约束
- 2 \leq N \leq 100
- 1 \leq W_i \leq 100
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N W_1 W_2 \cdots W_N
输出
打印答案。
示例输入 1
3 1 1 2
示例输出 1
4
有四种排列 p 满足条件: (1,3,2),(2,3,1),(3,1,2),(3,2,1)。 如果 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) 很重要。
示例输入 2
4 1 2 3 8
示例输出 2
0
示例输入 3
20 2 8 4 7 5 3 1 2 4 1 2 5 4 3 3 8 1 7 8 2
示例输出 3
373835282