D. 钢琴演奏家 - EOJ Monthly 2020.3

仪表盘所有提交榜单题解

单点时限: 1.5 sec

内存限制: 512 MB

Cuber QQ 在疫情期间已经宅在家两个月了。

实在是无所事事的他，决定重操旧业，继续实现他曾经梦寐的钢琴演奏家梦想。

掀开积满了灰尘的钢琴盖，是他许久都未触碰的琴键，按下的瞬间，他发现，钢琴坏了。

Cuber QQ 有一个多年的弹奏习惯，他弹奏钢琴，同一时刻一定会同时按下 $m$ 个琴键，他喜欢不同音调交织在一起的声音，可是现在不允许了。

可能是因为时间的原因，钢琴不支持琴键并行（音乐带师 Cuber QQ 发明的词汇）了。通俗来说，当 Cuber QQ 同时按下 $m$ 个琴键的时候，钢琴只会发出音调最高的那个琴键的声音。

不甘心的 Cuber QQ 开始尝试每一个 $m$ 键的组合。他会记录下每一次钢琴发出的音调，他会统计所有演奏出的音调之和，为了验证自己有没有算错，他邀请你来帮他再算一遍。

需要注意的是，因为钢琴坏了，所以可能存在相同音调的琴键。

由于这个和可能会很大，你只需要告诉 Cuber QQ 这个和模 $10^{9} + 7$ 的结果是多少。

输入数据第一行包含一个整数 $T$ ( $1 \leq T \leq 1000$ ) 表示数据组数。

对于每一组数据，第一行包含两个整数 $n$ , $m$ ( $1 \leq m \leq n \leq 10^{6}$ ) ，分表表示钢琴的琴键数量和每次同时按下的琴键个数。

第二行包含 $n$ 个整数 $a_{1}, a_{2}, \dots, a_{n}$ ( $0 \leq a_{i} \leq 10^{9}$ )，表示琴键的音调（可能会出现相同的音调）。

保证对于所有数据有 $\sum n \leq 10^{6}$ 。

对于每组数据输出一行，包含一个整数表示答案。

由于答案可能很大，需要对 $10^{9} + 7$ 取模。

Input

1
3 2
1 2 3

Output

NaN

比赛状态发生变化，点 OK 刷新。

OK

EOJ Monthly 2020.3