Background

最近小 $\omega$ 在学习博弈论。他在做一道经典题——取狮子游戏。

Description

提示：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

共有 $n$ 个狮子，第 $i$ 个狮子的「吼声」为 $a_i$。

如果 $k$ 个狮子 $(i_1, i_2 \dots i_k)$ 同时吼叫，那么它们的「组合吼声」为所有狮子吼声的最大值，即 $\max(a_{i_1}, a_{i_2}, \dots, a_{i_k})$。

求在所有的 $k$ 个狮子的组合中，「组合吼声」之和是多少。答案对 $998244353$ 取模。

形式化的：给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$，求：

Format

Input

本题共有 $T$ 组测试数据。

第一行输入一个整数表示 $T$。

对于每组数据，第一行两个整数 $n, k$，第二行 $n$ 个整数 $a_i$。

Output

对于每组数据，输出一个答案，对 $998244353$ 取模。

Samples

2
3 2
1 2 3
5 2
1 3 2 2 2

8
24

对于第一组数据，$\max(a_1, a_2) = 2, \max(a_1, a_3) = 3, \max(a_2, a_3) = 3$，因此答案为 $2 + 3 + 3 = 8$。

Limitation

本题开启捆绑测试。

对于 $100\%$ 的数据，$1 \le T \le 10$，$1 \le k \le n \le 2000$，$1 \le a_i \le 10^9$。