← Home
write a go solution for Description:
Alice and Bob are playing a game. There are n balls, out of which k are special. Each ball has a value associated with it.

The players play turn by turn. In each turn, the player randomly picks a ball and adds the value of the ball to their score, which is 0 at the beginning of the game. The selected ball is removed from the game. If the ball was special, the same player takes the next turn if at least one ball is remaining. If the ball picked was not special, the next player plays their turn.

They play this game until no balls are remaining in the game. Alice plays first.

Find the expected score that both the players have at the end of the game modulo 10^9+7.

Formally, let M=10^9+7. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are integers and qnotequiv0pmodM. Output the integer equal to p*q^-1bmodM. In other words, output such an integer x that 0<=x<M and x*qequivppmodM.

Input Format:
There are multiple test cases. The first line of the input contains an integer t, the number of test cases (1<=t<=2*10^5).

Each test case description is on a new line. The first line of the test case contains two integers n and k in the respective order separated by a space (1<=k<=n<=4*10^5).

The second line of the test case contains n integers: v_1,v_2,ldots,v_n, the value for each ball separated by spaces. The first k balls are special (1<=v_i<=10^7).

The sum of n over all test cases does not exceed 5*10^5.

Output Format:
Output two integers per test case in a new line, the expected score of Alice and the expected score of Bob modulo 10^9+7.

Note:
In the first test case, Alice's expected score is 45, and Bob's is 30 at the end of the game.. Output only the code with no comments, explanation, or additional text.