题目描述

神仙 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

2

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

5 3
3 1 1

30

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

4 4
1 1 1 1

72

可以证明可行的连边方案共有 $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$，图中无重边和自环。