3746. 钢琴演奏家

单点时限: 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\le T\le 1000$) 表示数据组数。

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

第二行包含 $n$ 个整数 $a_1,a_2,\ldots ,a_n$ ($0\le a_i\le 10^9$),表示琴键的音调(可能会出现相同的音调)。

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

输出格式

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

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

样例

Input
1
3 2
1 2 3
Output
8

376 人解决,622 人已尝试。

447 份提交通过,共有 3050 份提交。

3.3 EMB 奖励。

创建: 7 月,2 周前.

修改: 7 月,2 周前.

最后提交: 1 天前.

来源: EOJ Monthly 2020.3

题目标签