求满足以下条件的排列 $(P_1, \dots, P_N)$ 的数量，结果对 $998244353$ 取模：

• 存在一个整数 $i$ ($1 \le i < N$)，使得 $A_{P_1} + \dots + A_{P_i} = A_{P_{i+1}} + \dots + A_{P_N}$。

数据范围

• $2 \le N \le 100$
• $1 \le A_i \le 100$

输入格式

输入通过标准输入按以下格式给出：

$N$ $A_1 \ A_2 \ \dots \ A_N$

输出格式

输出答案。

样例

样例输入 1

3
4 9 5

样例输出 1

4

样例输入 2

2
100 100

样例输出 2

2

样例输入 3

8
3 2 6 3 1 2 4 5

样例输出 3

11520

说明

对于第一个样例： $(1, 2, 3)$ 的排列共有 $3! (= 6)$ 种，其中有 4 种满足条件：

• $(1, 3, 2)$
• $(2, 1, 3)$
• $(2, 3, 1)$
• $(3, 1, 2)$

例如，对于 $(1, 3, 2)$，选择 $i = 2$，我们有 $A_{P_1} + A_{P_2} = A_1 + A_3 = 4 + 5 = 9$，而 $A_{P_3} = A_2 = 9$，满足条件。