Pattern Sum

Given an array/list ‘Arr’, and two integers ‘A’ and ‘B’ which represent the number of 0’s and 1’s in the binary form, find the sum of all the numbers in the array ‘Arr’ having the same number of 0’s and 1’s in their binary representation.

The answer can be large so return answer modulo 1000000007

For Example

Let Arr[] = {2, 4, 10} , A = 1 and B = 1

In this example, the binary representation of the array {2, 4, 10} is {10, 100, 1010} and according to the problem statement, only 2 fulfills the given condition, i.e., have one 0-bit count and one 1-bit count. Hence, the sum of all the numbers is 2.

Note :

Do not count zeros to the left of the most significant set bit.

Input format :

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’ denoting the array’s length.

The second line of the test case contains two integers, ‘A’ and ‘B’, denoting the number of ‘0’ bits and ‘1’ bits, respectively.

The third line of the test case contains an array ‘Arr’ of ‘N’ integers.

Output format :

For each test case, print an integer denoting the sum of all numbers matching the given pattern.    

Output for each test case will be printed in a separate line.

Note:

 You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
0 <= Arr[i] <= 10^9
0 <= A <= 31
0 <= B <= 31
0 <= A + B <= 31

Time Limit: 1sec