题解

题面描述

给定一个长度为$n$的序列$a$，定义函数$f(A)$为序列$A$在从小到大排好序后第$k$个值。若$|A|<k$，则$f(A)=0$。求原序列$a$中所有子序列（不要求连续）的$f$值之和，对$998244353$取模。

输入包含多组测试数据。每组输入：

• 第一行：正整数$n,k$，满足$1\le k\le n\le 2\times10^{5}$。
• 第二行：$n$个正整数$a_i(1\le a_i\le10^9)$。

题目内容

给定一个长度为$n$的序列$a$，小笨想知道a中所有长度不小于$k$的子序列(不要求连续)的第$k$小值之和，请你算一算吧。

更正式的 定义$f(A)$为序列$A$在从小到大排好序后第$k$个值，即$A_k$，求$a$中所有子序列的$f$值之和。

(特别的:如果$A$的长度不足$k$，则$f(A)=0$)

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≦T≤100)$代表数据组数，每组 测试数据描述如下:

第一行两个正整数 $n,k$$(1≦k≦n≦2×10^5)$，分别表示序列$a$的长度以及$k$。

第二行$n$ 个正整数$a_i(1≦a_i≦10^9)$,表示$a$。

除此之外，保证单个测试文件的$n$之和不超过$2×10^5$

输出描述

对于每组测试数据:

在单独的一行输出一个整数，表示所有子序列$f$值之和。

(由于结果可能很大，因此输出结果对$998244353$取模的值。)

样例1

输入

2
6 3
1 2 3 4 5 6
3 1
2 2 2

输出

192
14

说明

对于第二组测试数据，{$2,2,2$}数组共有$7$个非空的子序列，所有子序列的$f$值都是$2$，因此输出 $2×7=14$