熟练的法师 Justin 花费多年时间收集了 $n$ 件神秘神器。每件神器都蕴含着一定量的能量，用一个非负整数表示。最近，Justin 偶然发现了一个名为“$k$-融合”的传奇咒语，据说该技术能将他的神器提升到前所未有的水平。

通过“$k$-融合”咒语，Justin 可以选取恰好 $k$ 件神器并将它们融合成一件新的神器。这件新合成的神器的能量等于被消耗的 $k$ 件神器的能量乘积。然而，这个过程是不可逆的，因为原始的 $k$ 件神器在融合后将永远消失。

Justin 决心使用这个咒语来制造出尽可能强大的神器。他执行了若干次（可能为零次）$k$-融合，以使他剩余神器中的最大能量值达到最大。完成后，Justin 要求你计算剩余神器中的最大能量值。

但这里有个转折！结果可能是一个天文数字，Justin 不想处理如此巨大的数值。相反，他要求你计算该最大能量值除以 $998244353$（他魔法研究中一个非常重要的质数）后的余数。

你能帮助 Justin 确定在他进行一系列 $k$-融合后，剩余神器中可能的最大能量值的余数吗？

输入格式

本题包含多个测试用例。输入的第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试用例的数量。

对于每个测试用例，输入包含两行。第一行包含两个整数 $n, k$ ($2 \le n \le 2 \times 10^5, 2 \le k \le n$)，分别表示神器的初始数量和 $k$-融合的参数。

第二行包含 $n$ 个非负整数 $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^9$)，其中 $p_i$ 是第 $i$ 件神器的能量。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示 Justin 挑战的答案。

样例

输入 1

3
8 3
44 5 2018 8 8 2024 8 28
5 4
4 5 5 1 0
5 2
0 0 0 0 0

输出 1

923923948
100
0