問題文

(1,\dots,N) の順列 (P_1,\dots,P_N) であって、以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。

• ある整数 i(1\le i\lt 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

入力例 1

3
4 9 5

出力例 1

4

(1,2,3) の順列は 3!(=6) 通りありますが、そのうち条件を満たすものは次の 4 つです。

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

例えば、 (1,3,2) は i=2 とすると A_1+A_3=A_2=9 であり、条件を満たしています。

入力例 2

2
100 100

出力例 2

2

入力例 3

8
3 2 6 3 1 2 4 5

出力例 3

11520