题目背景

原题链接

题目描述

小奔热衷于乘法，他最喜欢做的事情是：从一个有 $n$ 个元素的可重集中选出 $k$ 个数，并把这 $k$ 个数的乘积作为这个组合的分数。

小奔想试遍所有的这些组合，然后算出所有这些组合的分数之和。但是他还要出模拟赛虐爆我们这些蒟蒻，所以他只好把这个任务交给了你。

作为不良心的出题人，这题你还要将答案对 $10^9 + 7$ 取模。

输入格式

第一行两个正整数 $n,k$。
第二行 $n$ 个正整数 $a_i$，表示可重集中的元素。

输出格式

输出一行一个整数表示答案。

3 3
1 1 1

1

4 3
1 1 1 2

7

10 7
11 45 14 19 19 8 10 8 17 23

693404716

提示

【样例二解释】
有四种选择方案，一种是 $\{1,1,1\}$ 和三种都是 $\{1,1,2\}$，分数之和为 $7$。

【数据范围】
对于 $100\%$ 的数据，$1\le k \le n \le 1.2\times 10^5$，$1\le a_i \le 10^8$。