在一个 $s$ 个点的图中，存在 $s-n$ 条边，使图中形成了 $n$ 个连通块，第 $i$ 个连通块中有 aia_iai 个点。

现在我们需要再连接 $n-1$ 条边，使该图变成一棵树。对一种连边方案，设原图中第 $i$ 个连通块连出了 did_idi 条边，那么这棵树 $T$ 的价值为：

你的任务是求出所有可能的生成树的价值之和，对 $998244353$ 取模。

输入的第一行包含两个整数 $n,m$，意义见题目描述。

接下来一行有 $n$ 个整数，第 $i$ 个整数表示 aia_iai (1≤ai<998244353)(1\le a_i< 998244353)(1≤ai<998244353)。

• 你可以由 aia_iai 计算出图的总点数 $s$，所以在输入中不再给出 $s$ 的值。

输出包含一行一个整数，表示答案。

本题共有 $20$ 个测试点，每个测试点 $5$ 分。

• 
  

  
  $20\%$ 的数据中，$n\le 500$。
  

  
  


• 
  

  
  另外 $20\%$ 的数据中，$n\le 3000$。
  

  
  


• 
  

  
  另外 $10\%$ 的数据中，$n\le 10010,m=1$。
  

  
  


• 
  

  
  另外 $10\%$的数据中，$n\le 10015,m=2$。
  

  
  


• 
  

  
  另外 $20\%$ 的数据中，所有 aia_iai 相等。
  

  
  


• 
  

  
  $100\%$ 的数据中，n≤3×104,m≤30n \le 3\times 10^4,m \le 30n≤3×104,m≤30。
  

  
  

其中，每一个部分分的测试点均有一定梯度。