#1489. 翘课

翘课

题目描述

神仙 bn 又想翘数学课了!

一天,bn 想通过藏在机房里面来避免要上数学课的悲惨命运,于是他来到了学校那雄伟的信息楼。

进入楼内,bn 面前出现了 nn 个机房,不同的机房之间有一些道路把它们相连。不仅如此,bn 还发现了一个奇怪的规律:有一些机房两两之间总存在一条道路,却和其它机房没有任何道路相连。

bn 决定运用离散数学的知识来分析自己的逃跑路径。

简单来说,这 nn 个机房可以看作一个有 nn 个节点的简单无向图,图中存在 kk 个联通块,第 ii 个联通块的大小是 sis_i;每一个独立的联通块都是一个完全图,即联通块内所有节点两两相连。为了逃跑方便,bn 想在图中新加入 k1k-1 条边,使得整张图联通。

bn 不想在“连边”(即修建新的道路)上花费太多的时间,因此他定义了某种连边方案 TT 的价值函数 val(T)val(T) 如下:

  • 设该方案内,kk 个联通块向外连出的边数分别为 d1,d2,,dkd_1,d_2,…,d_k,则 val(T)=i=1kdi!val(T)=\prod\limits_{i=1}^kd_i!,其中 \prod 表示连乘。

现在 bn 想知道,若给定机房对应的图,那么所有可行连边方案的价值之和是多少呢?

这下子 bn 不会了,他想问问你。

由于这个数很大,你只需要输出它对 998244353998244353 取模之后的结果即可。

输入格式

为了减少输入量,我们规定第ii个联通块内的节点编号依次为 $\sum\limits_{j=1}^{i-1}s_j+1,\sum\limits_{j=1}^{i-1}s_j+2,…,\sum\limits_{j=1}^{i-1}s_j+s_i$ ,因此不再输入每个联通块内的节点编号。

第一行两个整数 n,kn,k,表示机房的数量和联通块数;

第二行k个整数 s1,s2,...,sks_1,s_2,...,s_k ,表示每个联通块的大小。

输出格式

一行一个正整数,表示所有可行连边方案的价值之和,答案对 998244353998244353 取模。

样例 1

3 2
2 1
2

连边方案共有两种,即连 (1,3)(1,3) 或连 (2,3)(2,3)。两种方案的价值均为 1×1=11×1=1,因此输出 22

5 3
3 1 1
30

可以证明可行的连边方案共有 1515 种,价值均为 1×1×2!=21×1×2!=2,因此输出 3030

4 4
1 1 1 1
72

可以证明可行的连边方案共有 1616 种,其中价值为 1×2!×2!×1=41×2!×2!×1=4 的有 1212 种,价值为 1×1×1×3!=61×1×1×3!=6 的有 44 种,因此输出 4×12+6×4=724×12+6×4=72

数据范围与提示

数据规模

对于 10%10\% 的数据,保证 n10n≤10

另有 10%10\% 的数据,保证 k2k≤2

对于 40%40\% 的数据,保证 k100k≤100

对于 60%60\% 的数据,保证 k1000k≤1000

另有 20%20\% 的数据,保证所有的 sis_i 均为 11

对于 100%100\% 的数据,保证 n109,k7000,1<kn,1si109n≤10^9,k≤7000,1<k≤n,1≤s_i≤10^9si=n∑s_i=n,图中无重边和自环。