Maximal AND Subsequences Problem

Given an array consisting of N integers, your task is to determine how many k-element subsequences of the given array exist where the bitwise AND of the subsequence's elements is maximal. Your objective is to find both the maximal AND value and the count of such subsequences.

Input:

integer T  # number of test cases
integer N, K  # size of array, length of subsequences for each test case
array of N integers  # elements of the array for each test case

Output:

integer maximal_AND_value, count_of_subsequences

Example:

Consider the array [1, 3, 6, 7] with K = 3.

Possible 3-element subsequences are: {1, 3, 6}, {1, 3, 7}, {1, 6, 7}, {3, 6, 7}.
Subsequences AND values: 0, 1, 0, 2.
Maximal AND value = 2, with 1 subsequence {3, 6, 7} achieving this value.

Constraints:

• 1 ≤ T ≤ 10
• 2 ≤ N ≤ 5 * 104
• 2 ≤ K ≤ N
• 0 ≤ Arr[i] ≤ 108

Note:

Since the number of k-element subsequences with the maximal AND value can be very large, provide the answer modulo 1000000007. You do not need to print anything. Just return an array of size two, where the first element is the maximal AND value, and the second element is the count of subsequences with this value.