CF1475E Advertising Agency

Masha 在一家广告公司工作。为了推广新品牌，她想与一些博主签订合同。Masha 总共认识 $n$ 个不同的博主。编号为 $i$ 的博主有 $a_i$ 个粉丝。 由于预算有限，Masha 只能与 $k$ 个不同的博主签约。当然，Masha 希望她的广告能被尽可能多的人看到。因此，她必须雇佣粉丝总数最多的博主。 请你帮助她，计算有多少种选择 $k$ 个博主的方式，使得他们的粉丝总数最大。只要两种方式中至少有一个博主不同，就认为这两种方式不同。Masha 认为所有博主的粉丝都是不同的（即没有粉丝会同时关注两个不同的博主）。 例如，如果 $n=4$，$k=3$，$a=[1, 3, 1, 2]$，那么 Masha 有两种方式选择 $3$ 个博主，使得粉丝总数最大： - 与编号为 $1$、$2$ 和 $4$ 的博主签约，此时粉丝总数为 $a_1 + a_2 + a_4 = 6$。 - 与编号为 $2$、$3$ 和 $4$ 的博主签约，此时粉丝总数为 $a_2 + a_3 + a_4 = 6$。 由于答案可能很大，请输出对 $10^9+7$ 取模后的结果。

第一行包含一个整数 $t$（$1 \le t \le 1000$）——测试用例的数量。接下来是 $t$ 个测试用例。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 1000$）——博主的数量以及可以签约的博主数量。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）——每个博主的粉丝数量。 保证所有测试用例中 $n$ 的总和不超过 $1000$。

对于每个测试用例，单独一行输出一个整数，表示选择 $k$ 个博主使得粉丝总数最大的方法数。

样例在题目描述中已给出解释。 在第二个测试用例中，以下方式均为有效选择： - 与编号为 $1$ 和 $2$ 的博主签约，此时粉丝总数为 $a_1 + a_2 = 2$； - 与编号为 $1$ 和 $3$ 的博主签约，此时粉丝总数为 $a_1 + a_3 = 2$； - 与编号为 $1$ 和 $4$ 的博主签约，此时粉丝总数为 $a_1 + a_4 = 2$； - 与编号为 $2$ 和 $3$ 的博主签约，此时粉丝总数为 $a_2 + a_3 = 2$； - 与编号为 $2$ 和 $4$ 的博主签约，此时粉丝总数为 $a_2 + a_4 = 2$； - 与编号为 $3$ 和 $4$ 的博主签约，此时粉丝总数为 $a_3 + a_4 = 2$。 在第三个测试用例中，以下方式为有效选择： - 与编号为 $2$ 的博主签约，此时粉丝总数为 $a_2 = 2$。 由 ChatGPT 4.1 翻译