Sum of Products of Combinations

Given a list of integers and two parameters N and K, compute the sum of products of all possible combinations of exactly K numbers chosen from the list. For example, if the list is A = [a₁, a₂, ..., àN;], then the answer is given by:

$$ \sum_{1 \le i_1 < i_2 < \cdots < i_K \le N} a_{i_1}a_{i_2}\cdots a_{i_K} $$

This needs to be calculated for each test case.

inputFormat

The input begins with an integer T (1 ≤ T ≤ 100) denoting the number of test cases. Each test case consists of two lines:

• The first line contains two space-separated integers N and K (1 ≤ K ≤ N ≤ 20), where N is the number of elements in the list.
• The second line contains N space-separated integers, each between -100 and 100.

outputFormat

For each test case, output a single line containing the sum of products of all combinations of K numbers from the list.

## sample

2
4 2
1 2 3 4
3 3
5 6 7

35
210

</p>