大户爱的幂和
题号：NC318444
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

大户爱有 N 个底数，第 i 个底数为 a_{i}。大户爱需要给每个底数分配不小于 0 的整数指数，第 i 个底数分配不小于 0 的整数指数 b_{i}，满足 b_i 之和为 M 且 a_i^{b_i} 之和最大。
因为 a_i^{b_i} 之和可能很大，你需要输出 a_i^{b_i} 之和的最大值对 998244353 取模后的结果，即 F\bmod 998244353。注意要求取模前的结果最大而非取模后的结果最大。
形式化的，你需要输出 F\bmod 998244353，满足：
\begin{aligned}<br />\max &&& F=\sum_{i=1}^{N}a_i^{b_i} \\<br />\mathrm{s.t.} &&& \sum_{i=1}^{N}b_i=M \\<br />&&& b_i\in \mathbb Z_{\geq 0} && i=1,2,\cdots,N<br />\end{aligned}

输入描述:

第一行一个整数 T (1\leq T \leq 10)，表示数据组数。
对于每组数据，第一行两个整数 N,M (1 \leq N,M\leq 10^5)，表示有 N 个底数，指数之和必须等于 M。
第二行 N 个整数 a_1, a_2, \cdots, a_N (1 \leq a_{i}<998244353)，表示底数。

输出描述:

对于每组数据，输出一行一个整数，表示答案对 998244353 取模后的结果。
示例1

输入

复制 
2
2 3
1 2
5 5
1 1 1 1 1

输出

复制 
9
5