题目描述

我们有 $N$ 个橙子，编号从 $1$ 到 $N$。第 $i$ 个橙子的重量为 $W_i$。高桥和青木将按照以下方式分享这些橙子：

• 选择一个排列 $(p_1, p_2, \cdots, p_N)$，其中 $(p_1, p_2, \cdots, p_N)$ 是 $(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