E. Я люблю шары
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. Имеется $$$n$$$ шаров, из которых $$$k$$$ — особенные. Каждый шар имеет свою стоимость.

Игроки играют по очереди. В каждый ход игрок случайным образом выбирает шар и прибавляет его стоимость к своему счету, который в начале игры равен $$$0$$$. Выбранный шар удаляется из игры. Если шар был особенным, следующий ход делает тот же игрок, если в игре остался хотя бы один шар. Если выбранный шар не был особенным, следующий игрок делает свой ход.

Они играют так до тех пор, пока в игре не останется ни одного шара. Алиса ходит первой.

Найдите ожидаемое количество очков, которое оба игрока получат в конце игры, по модулю $$$10^9+7$$$.

Формально, пусть $$$M = 10^9+7$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$p$$$ и $$$q$$$ — целые числа, и $$$q \not \equiv 0 \pmod{M}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 4 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел: $$$v_1, v_2, \ldots, v_n$$$ — стоимости шаров. Первые $$$k$$$ шаров являются особенными ($$$1 \le v_i \le 10^7$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке по два целых числа: ожидаемый счёт Алисы и ожидаемый счёт Боба по модулю $$$10^9+7$$$.

Примеры
Входные данные
1
5 2
10 20 5 15 25
Выходные данные
45 30
Входные данные
5
1 1
732507
2 2
5817860 5398510
5 1
2122894 4951549 2750585 7821535 3214167
8 4
1405323 5069867 6883092 6972029 328406 2478975 7628890 9973340
4 2
9662050 3566134 3996473 9872255
Выходные данные
732507 0
11216370 0
810642660 210218077
722402997 318336932
349086489 678010430
Входные данные
5
3 3
1095611 8219204 7773462
2 1
8176490 2774103
3 1
9178636 5138057 3367761
12 9
7597698 6843019 2298534 1522386 4969588 1340345 3967362 9152890 6689668 9986080 4745473 7407325
10 5
6986368 2397882 5804127 6980694 3740836 3215836 5195724 3179261 4136769 4544231
Выходные данные
17088277 0
6862348 4088245
677038671 340645790
36949997 29570371
725118051 321063684
Примечание

В первом наборе входных данных ожидаемый счёт Алисы равен $$$45$$$, а Боба — $$$30$$$.