The city hall of Lucban made lots of kiping, or rice wafers, as part of their yearly Pahiyas Festival. The festival is for expressing gratitude for a bountiful harvest, much like the similar holiday of Thankskiping.
Last year, Isidro was in charge of distributing kiping. But because there was so much to give away, kiping track of the inventory took a long time. This year, in order to reduce waiting time, Isidro decided to have several lines for distribution.
There are $$$n$$$ people who want kiping, and the $$$i$$$th person wants $$$a_i$$$ wafers of kiping. Helping Isidro are $$$k$$$ people handling distribution, or in other words, shopkiping. Each of the $$$k$$$ shopkeepers can give kiping at a rate of one wafer per second.
Isidro wants to arrange the $$$n$$$ people into $$$k$$$ lines, one for each shopkeeper. When a person is at the front of the line, they take $$$a_i$$$ kiping, which will take $$$a_i$$$ seconds. After the shopkeeper is done kiping away their kiping, the next person in line receives their kiping.
A person's waiting time is how long they have to wait, in seconds, before they start receiving kiping. In other words, it is the sum of the $$$a_i$$$ of everyone lined up in front of them. Isidro wants to arrange people into lines so that everyone's total waiting time as small as possible. And for bookkiping purposes, he also wants to know how many ways there are to arrange the people such that the total waiting time is as small as possible.
Help Isidro compute these two numbers. Since both answers can be very large, output both answers modulo $$$10^9 + 7$$$.
Two arrangements are distinct if the sequence of people lined up in some cashier in the first arrangement is different from the sequence of people lined up in the corresponding cashier in the second arrangement.
The first line of input contains $$$t$$$, the number of test cases.
The first line of each test case contains two space-separated integers $$$n$$$ and $$$k$$$. The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$.
For each test case, print a single line containing two space-separated integers denoting the answer. The first integer should be the minimum sum of everyone's waiting times, and the second integer should be the number of distinct ways to arrange people to achieve this. Since both answers can be very large, output both answers modulo $$$10^9 + 7$$$.
$$$1 \le t \le 100$$$
$$$1 \le n \le 10^5$$$
$$$1 \le k \le 10^5$$$
$$$1 \le a_i \le 10^9$$$
The sum of $$$n$$$s in a single test file is at most $$$10^5$$$.
Subtask 1 (7 points):
$$$k \ge n$$$
Subtask 2 (7 points):
$$$1 \le n \le 6$$$
$$$1 \le k \le 3$$$
Subtask 3 (19 points):
$$$k = 1$$$
Subtask 4 (23 points):
All the $$$a_i$$$ are distinct.
$$$1 \le n \le 10$$$
$$$1 \le k \le 3$$$
Subtask 5 (27 points):
All the $$$a_i$$$ are distinct.
Subtask 6 (17 points):
No additional restrictions.
1 1 1 1
0 1
3 3 2 2 5 8 3 3 2 5 8 3 4 2 5 8
2 4 0 6 0 24
In the first test case, it can be shown that the minimum sum of everyone's waiting times is $$$2$$$. There are $$$4$$$ different ways to achieve this:
In the first way in the picture above, person 1 waits $$$0$$$ seconds, person 2 waits $$$2$$$ seconds, and person 3 waits $$$0$$$ seconds, making a total of $$$2$$$ seconds.
In the second test case, it can be shown that the minimum sum of everyone's waiting times is $$$0$$$, and there are $$$6$$$ different ways to achieve this:
Similar reasoning can be applied for the third test case.
