← 返回题目列表

Codeforces · 1475/E

E. 广告公司

中文机器翻译题面 查看原题

玛莎在一家广告公司工作。为了推广新品牌,她想与一些博主签约。总的来说,玛莎与 $$$n$$$ 不同的博主有联系。编号为 $$$i$$$ 的博主拥有 $$$a_i$$$ 关注者。

由于玛莎的预算有限,她只能与$$$k$$$不同的博主签订合同。当然,玛莎希望她的广告被尽可能多的人看到。因此,她必须聘请粉丝总数最多的博主。

帮助她,找到选择 $$$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

3
4 3
1 3 1 2
4 2
1 1 1 1
2 1
1 2

输出 #1

2
6
1

注意

测试用例在语句中进行了解释。

在第二个测试用例中,以下方式有效:

- 与编号为 $$$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$$$。