Lottery Balls

We gladly thank Clive Fraser for creating this problem!

Ann and Bob have been working for a local lottery where numbered balls are drawn at random to provide the winning number sequences. New balls are used every time a draw is made, so Ann and Bob have a plentiful supply of numbered balls.

Ann and Bob thought that they could use the supply of numbered balls to devise a gambling game. After some discussion they came up with the following rules.

The game starts with N numbered balls, each carrying a different number. A sequence of M balls is drawn at random, but balls are replaced after being drawn, so the same ball can be drawn multiple times. When the sequence of M numbers has been selected, the numbers are sorted into numerical order, from the largest to the smallest. A score is then calculated by multiplying the numbers on the balls (in their sorted order) by the values 1, 2, 4, 8, 16, 32, 64, ... The total of these weighted numbers is the score. Note that the weights are doubling as we move from ball to ball. Several people can take it in turns to obtain a random sequence of M numbers by randomly selecting the balls and using the weightings to calculate their score. The person with the highest score then wins.

Suppose that N = 10, so that there are 10 numbered balls. Suppose that the numbers on these balls are {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}. Suppose that M = 8, so we need to select a random sequence of 8 balls. One possible sequence is {7, 3, 15, 9, 3, 11, 11, 5}. In order to calculate the score we sort this sequence into descending order. This gives {15, 11, 11, 9, 7, 5, 3, 3}. Next we apply the multipliers to get the weighted total:

1 x 15 + 2 x 11 + 4 x 11 + 8 x 9 + 16 x 7 + 32 x 5 + 64 x 3 + 128 x 3 = 1001

Other scores are calculated in a similar way.

After playing the game for some time, Ann and Bob became interested in the distribution of the scores. It was obvious that different randomly chosen sequences could give rise to the same score. They decided to investigate the relationship between the initial sequence and the score it produces. They began by looking at small examples. Consider the case where N = 3 and M = 3 and the numbers on the balls are {3, 5, 7}. Ann and Bob generated every possible sequence of 3 randomly chosen balls and worked out the scores for each of these. The results for the 27 different sequences are shown in the table below. The first column shows the randomly chosen sequence. The second column shows the sorted version of this sequence. The third column shows the score for the sequence, after using the multipliers 1, 2 and 4.

{3, 3, 3}    {3, 3, 3}    21
{3, 3, 5}    {5, 3, 3}    23
{3, 3, 7}    {7, 3, 3}    25
{3, 5, 3}    {5, 3, 3}    23
{3, 5, 5}    {5, 5, 3}    27
{3, 5, 7}    {7, 5, 3}    29
{3, 7, 3}    {7, 3, 3}    25
{3, 7, 5}    {7, 5, 3}    29
{3, 7, 7}    {7, 7, 3}    33
{5, 3, 3}    {5, 3, 3}    23
{5, 3, 5}    {5, 5, 3}    27
{5, 3, 7}    {7, 5, 3}    29
{5, 5, 3}    {5, 5, 3}    27
{5, 5, 5}    {5, 5, 5}    35
{5, 5, 7}    {7, 5, 5}    37
{5, 7, 3}    {7, 5, 3}    29
{5, 7, 5}    {7, 5, 5}    37
{5, 7, 7}    {7, 7, 5}    41
{7, 3, 3}    {7, 3, 3}    25
{7, 3, 5}    {7, 5, 3}    29
{7, 3, 7}    {7, 7, 3}    33
{7, 5, 3}    {7, 5, 3}    29
{7, 5, 5}    {7, 5, 5}    37
{7, 5, 7}    {7, 7, 5}    41
{7, 7, 3}    {7, 7, 3}    33
{7, 7, 5}    {7, 7, 5}    41
{7, 7, 7}    {7, 7, 7}    49

Ann and Bob worked out that the total of all the scores for this example is 837. They began to discuss how easy it would be to calculate the total score for all possible random sequences, in the general case.

In this problem you will be given several examples of N balls, requiring a random selection of M numbers from the set of numbers on the balls. In each case you need to calculate the total score for every possible sequence which can be randomly selected. The total score can be quite large so you are asked to give the answer modulo 1000000007 (10^9 + 7). The value of N will not exceed 35 and the value of M will not exceed 110.

Input/Output description: The first line of the input data will contain a single integer P indicating the number of problems to be solved. Each problem has 2 lines of data. The first of these contains 2 space-separated integers N and M, for the number of balls and the number of values selected. The second line contains N space-separated integers which are the numbers on the N balls. Your answer is the total score for all possible sequences of length M (modulo 1000000007). Combine all answers into a single string, separated by single spaces.

Example:

input:
3
3 3
3 5 7
8 4
2 3 5 7 8 10 11 13
11 16
1 2 6 7 9 10 13 15 16 20 21

answer:
837 335543 164697049