#6732. 翘课

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ce-amtic

题目描述

神仙 bn 又想翘数学课了!

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

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

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

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

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

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

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

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

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

输入格式

为了减少输入量,我们规定第 i 个联通块内的节点编号依次为 \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,k ,表示机房的数量和联通块数;

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

输出格式

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

样例

样例输入 1

3 2
2 1

样例输出 1

2

样例解释 1

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

样例输入 2

5 3
3 1 1

样例输出 2

30

样例解释 2

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

样例输入 3

4 4
1 1 1 1

样例输出 3

72

样例解释 3

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

数据范围与提示

数据规模

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

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

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

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

另有 20\% 的数据,保证所有的 s_i 均为 1

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