联通

题号：NC218220
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一张 n 个节点的简单无向图，满足图中存在 k 个联通块，其中第i 个联通块的大小是 $s_i$ 。每一个独立的联通块内所有节点两两相连。

你需要在图中新加入 k-1 条边，使得整张图联通。定义某种连边方案 T 的价值函数 val(T) 如下：

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

现在你需要求出所有可行连边方案的价值之和。由于这个数很大，你只需要输出它对 998244353 取模之后的结果即可。

第一行两个整数 n,k，表示节点的数量和联通块数；

第二行k个整数 $s_1\text{~} s_k$ ，表示每个联通块的大小。

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

示例1

复制

3 2
2 1

复制

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

示例2

复制

5 3
3 1 1

复制

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

示例3

复制

4 4
1 1 1 1

复制

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

对于100%的数据，保证 $1≤n≤10^9,1<k≤7000,k≤n,1≤s_i≤10^9$ 且 $∑s_i=n$ 。