题目背景

你们居然挺过来了，真是令人难以置信，不是吗？

努力的过程还是挺有意思的。

这个嘛，

你又在等什么？

题目描述

Madeline 将收集到的草莓分给了朋友们

火红色的草莓和金黄色的草莓交错在一起，很受朋友们喜爱

朋友们为了感谢 Madeline ，一起收集了许多五颜六色的珠子，打算串成一条花花绿绿的项链送给 Madeline

经过朋友们的精心准备，现在桌子上摆着$n$个珠子，这些珠子一共有$k$种颜色。具体来说，第$i$种颜色的珠子有$a_i$个

看着桌子上晶莹剔透的珠子，现在朋友们却犯难了，因为他们不知道怎样将它们串在一起才最美丽

朋友们向你发出了请求，需要你帮忙求出本质不同的方案总数

朋友们分不清这些珠子的顺序，因此两个珠子不同仅当它们的颜色不同

这条项链必须是完整的，因此所有珠子构成了一个连通块

这条项链还不能太杂乱，因此所有珠子必须构成一棵基环树

在多次询问 Madeline 的朋友们之后，你发现这棵基环树的两个子树不同仅当它们对应点的颜色不同或者这两棵子树不同构。对于不同的子树是有先后顺序之分的

举例来说，下面的几种部分串法是互不相同的

朋友们的时间很紧迫，因此如果两种项链能够通过旋转基环得到同样的结果，那么这两种项链本质上是相同的

输入格式

第一行两个整数 $n, k$，分别表示珠子的总数以及颜色种数

接下来一行 $k$ 个整数 $a_i$，表示每种颜色的珠子个数

输出格式

输出一个整数，表示方案数模 $998244353$ 的余数

3 3
1 1 1

8

4 2
1 3

15

提示

基环树：一个有$n$个点$n$条边的联通图，没有自环。容易看出这样的图是一个环上连出了一些树

基环：基环树中的环

对于 $5\%$ 的数据，$n \leq 8$

对于另 $10\%$ 的数据，$k = 1 , n \leq 10^3$

对于前 $30\%$ 的数据，$n \leq 10^3$

对于另 $20\%$ 的数据，$k = 1 , n \leq 5 \times 10^4$

对于前 $80\%$ 的数据，$n \leq 5 \times 10^4$

对于 $100\%$ 的数据，$ a_i > 0 , \sum a_i = n , n \leq 2 \times 10^5 , k \leq n $

第二个样例解释：

有如下$15$种情况：