题目描述

有一张图,顶点分为$n$个部分,对于任意两个部分$A$,$B$,$A\neq B$,对于任意点$a\in A$,$b\in B$,有一条$(a,b)$之间的无向边 除此之外不存在其他的边,求该图的生成树数量,对$998244353$取模

输入格式

一行一个正整数$n$,表示图的点的部分数量

接下来一行$n$个正整数$a_1$,$a_2$,$a_3$...$a_n$表示每个部分的点数

输出格式

一行一个非负整数$ans$,表示答案对$998244353$取模的结果

样例输入1

2

2 2

样例输出1

4

样例输入2

7

11 45 14 19 19 8 10

样例输出2

588627480

数据范围

对于$20\%$的数据,$n,\sum_{i} a_i\le 100$

对于另外$20\%$的数据,$n=2$

对于$100\%$的数据,$2\le n\le 200000$,$a_i < 998244353$