龙
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

在小红还是网瘾少女的时候特别爱玩一款网游，叫《龙Online》

随着时间推移，热门的游戏逐渐冷却，小红的青春也一起随风而散了。

龙Online 中的法器有一个宝珠系统，法器中有 � 个宝石孔，小红有 � 个不同的宝石，第 � 个宝石可以提升 �� 点战斗力。

但是这个系统有个特点，每次镶嵌宝石，被选中的宝石会随机选择一个宝石孔进去，如果这个孔原来有宝石，原来的宝石将会被毁坏。

小红可以任意决定镶嵌宝石的顺序，她想知道，如果把这 � 颗宝石都镶嵌进去，期望战力提升的最大值是多少？

答案对 998244353 取模。


输入描述:

第一行两个整数 n,m(1\leq n,m\leq 10^6),分别表示宝石的个数和宝石孔的个数

第二行 n 个整数 a_1\sim a_n(1\leq a_i\leq 10^9)，表示第i个宝石提升的战力

输出描述:

一个整数，表示期望战力提升的最大值，对998244353取模
示例1

输入

复制 
3 2
1 2 3

输出

复制 
748683269

说明

样例解释：
将宝石按 1,2,3 顺序嵌入

每个宝石都有 2 个孔可能进入，所以有 2^3=8 种情况，留下的宝石分别是：(3),(2,3),(2,3),(1,3),(1,3),(2,3),(2,3),(3)。期望收益是\frac{17}{4}，对998244353取模后的结果为748683269

注意取模

1\leq n,m\leq 10^6

1\leq a_i\leq 10^9。

备注:

说明：最终的答案一定可以表示成两个互质整数之比的形式。而对于一个分数\frac{a}{b}来说，我们要表示为a\cdot b^{-1}的形式，即a与b在模998244353意义下的逆元的积的形式，而b^{-1}可由费马小定理得出，即：
b^{-1}\equiv b^{p-2}\pmod{p}，其中p为质数，那么答案可以表示为a*b^{p-2},此处p=998244353