CF1475E.Advertising Agency

Masha works in an advertising agency. In order to promote the new brand, she wants to conclude contracts with some bloggers. In total, Masha has connections of $n$ different bloggers. Blogger numbered $i$ has $a_i$ followers.

Since Masha has a limited budget, she can only sign a contract with $k$ different bloggers. Of course, Masha wants her ad to be seen by as many people as possible. Therefore, she must hire bloggers with the maximum total number of followers.

Help her, find the number of ways to select $k$ bloggers so that the total number of their followers is maximum possible. Two ways are considered different if there is at least one blogger in the first way, which is not in the second way. Masha believes that all bloggers have different followers (that is, there is no follower who would follow two different bloggers).

For example, if $n=4$, $k=3$, $a=[1, 3, 1, 2]$, then Masha has two ways to select $3$ bloggers with the maximum total number of followers:

• conclude contracts with bloggers with numbers $1$, $2$ and $4$. In this case, the number of followers will be equal to $a_1 + a_2 + a_4 = 6$.
• conclude contracts with bloggers with numbers $2$, $3$ and $4$. In this case, the number of followers will be equal to $a_2 + a_3 + a_4 = 6$.

Since the answer can be quite large, output it modulo $10^9+7$.

玛莎在一家广告公司工作。为了推广新品牌，她希望与一些博主签订合同。玛莎总共联系了 $n$ 位不同的博主。编号为 $i$ 的博主拥有 $a_i$ 名粉丝。

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

请帮助她计算：有多少种方式从中选出 $k$ 位博主，使得他们的粉丝总数达到最大可能值？若两种方案中至少存在一位博主只属于其中一种方案，则认为这两种方案不同。玛莎认为所有博主的粉丝互不重叠（即不存在某位粉丝同时关注两位不同的博主）。

例如，若 $n=4$，$k=3$，$a=[1, 3, 1, 2]$，则玛莎有两种方式选出 $3$ 位博主，使其粉丝总数达到最大值：

• 与编号为 $1$、$2$ 和 $4$ 的博主签订合同。此时粉丝总数为 $a_1 + a_2 + a_4 = 6$。
• 与编号为 $2$、$3$ 和 $4$ 的博主签订合同。此时粉丝总数为 $a_2 + a_3 + a_4 = 6$。

由于答案可能非常大，请将结果对 $10^9+7$ 取模后输出。

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 1000$) — the number of bloggers and how many of them you can sign a contract with.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots a_n$ ($1 \le a_i \le n$) — the number of followers of each blogger.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

第一行包含一个整数 $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$。

For each test case, on a separate line output one integer — the number of ways to select $k$ bloggers so that the total number of their followers is maximum possible.

对于每个测试用例，在单独一行输出一个整数——选择 $k$ 个博主的方法数，使得他们的粉丝总数达到最大可能值。

The test case is explained in the statements.

In the second test case, the following ways are valid:

• conclude contracts with bloggers with numbers $1$ and $2$. In this case, the number of followers will be equal to $a_1 + a_2 = 2$;
• conclude contracts with bloggers with numbers $1$ and $3$. In this case, the number of followers will be equal to $a_1 + a_3 = 2$;
• conclude contracts with bloggers with numbers $1$ and $4$. In this case, the number of followers will be equal to $a_1 + a_4 = 2$;
• conclude contracts with bloggers with numbers $2$ and $3$. In this case, the number of followers will be equal to $a_2 + a_3 = 2$;
• conclude contracts with bloggers with numbers $2$ and $4$. In this case, the number of followers will be equal to $a_2 + a_4 = 2$;
• conclude contracts with bloggers with numbers $3$ and $4$. In this case, the number of followers will be equal to $a_3 + a_4 = 2$.

In the third test case, the following ways are valid:

• concludes a contract with a blogger with the number $2$. In this case, the number of followers will be equal to $a_2 = 2$.

测试用例的说明见题目描述。

在第二个测试用例中，以下方案是合法的：

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