A and B are getting bored so they decide to play a game with an array X of n elements with A starting the game. In each turn : A player selects some or all elements from array X with the same value and removes them from array X - The player whose turn makes array X becomes empty wins the game.

B being clever, modifies the game. He decides to select some distinct elements (among those present in array X[]) and deletes all other elements which are not selected from X. The game is then played using this modified array. For example, consider X=[1,2,1,3,4,8,6,2]. If B chooses values (3,4,2), then the modified array with which the game is played is [1,1,8,6,2]. 

Both A and B play optimally. Find the number of possible subsets of elements that B can select to modify X[] such that B is bound to win.

Print the answer modulo 10^9+7,since the number of possible subsets can be large.Consider an empty subset as a valid answer.

Input Format
•	First line contains an integer t denoting the number of test cases.
•	Second line contains an integer n.
•	Next line contains n elements of X[].
Constraints
•	1 <= t <= 10
•	1 <= N <= 2*10^5
•	1 <= X[i] <= 10^18

Output Format
Print the number of possible subsets B can choose in a new line. Print the ans modulo 10^9+7.


My code works for small test cases but with large ones, it gives timeout. I am creating a frequency array i.e after sorting the given array, I count all the occurrences of a single number and put that count in another array. Then I generate a bit mask for the frequency array. We can only remove distinct elements (only one from each frequency). If bit is 1 - decrease its frequency by one and if it 0 then leave it.

Ex:- arr = {1,1 ,2,2,3} 
then frequency arr = { 2, 2, 1}
if bit mask is 011 then frequency arr becomes {2,1,0}

then with recursion , I decide whether B will win , if he wins increment the ans by 1.


My Code:-

long long int exp(long long int x, long long int n)
{
    long long int res = 1;
    while (n != 0)
    {
        if (n & 1)
        {
            res = (res * 1LL * x);
        }
        x = (x * 1LL * x);
        n = n >> 1;
    }
    return res;
}
bool func(int arr[], int &n, int &count)
{
    if (count == 0)
    {
        return false;
    }
    if (count == 1)
    {
        return true;
    }
    bool ans = 0;
    for (int i = 0; i < n; i++)
    {
        int x = arr[i];
        for (int j = 1; j <= x; j++)
        {
            arr[i] -= j;
            count -= j;
            ans = ans || !func(arr, n, count);
            arr[i] += j;
            count += j;
        }
    }
    return ans;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        long long int arr[n];
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
        }
        sort(arr, arr + n);
        vector<int> v;
        v.reserve(200000);
        v.push_back(1);
        for (int i = 1; i < n; i++)
        {
            if (arr[i - 1] == arr[i])
            {
                v[v.size() - 1]++;
            }
            else
            {
                v.push_back(1);
            }
        }
        
        ll ans = 0;
        int temp[v.size()];
        for (int i = 0; i < v.size(); i++)
        {
            temp[i] = v[i];
        }
        int count = 0;
        for (int i : v)
        {
            count += i;
        }
        int count_temp = count;
        for (long long int i = 0; i < exp(2, v.size()); i++)
        {
            long long int t = i;
            int mul = 0;
            while (t != 0)
            {
                if (t & 1)
                {
                    temp[mul]--;
                    count_temp--;
                }
                t = t >> 1;
                mul++;
            }
            if (!func(temp, n, count_temp))
            {
                ans++;
            }
            for (int j = 0; j < v.size(); j++)
            {
                temp[j] = v[j];
            }
            count_temp = count;
        }
        cout << ans%std_modulo << "\n";
    }
}

The problem statement is:-

Two sequences A and B are said to be compatible if A can be converted to B in any number of moves of the following type:

- Replace any element of the sequence with -1*(S) where S is equal to the sum of all elements in the current sequence.

Now, given two sequences X and Y. Count the number of subsequences of X that are compatible with Y . Print the answer modulo 109+7

Input
Each test contains multiple test cases. The first line contains the number of test cases, T. The description of the test cases follows.

The first line of each test case contains two integers n, m where n and m are the sizes of the sequence X and Y respectively.

The second line of each test case contains n integers X1, X2,. , Xn

The third line of each test case contains m integers Y1, Y2,. , Ym.

Constraints:
1 <= T <= 500
1 <= m <= n <= 2*105
-109 <= Xi, Yi <= 109
The sum of n over all test cases is less than or equal to 2*105
Output
For each test case print an integer, the number of subsequences of X which are compatible with Y modulo 109+7.

Two subsequences are compatible if they are permutations of each other , since after replacing for the first time, we have as 'sum of the subsequence' -(the element replaced) and it can be exchanged with any other element thereby making it the new sum. And at last we can put an element of the subsequence at the place where the first sum was placed.

Ex:- 7 4 2       sum of subsequence is 13
     2 7 4
replacing 7 with -13 ,  -13 4 2 (new sum is  -(the element replaced) i.e -7)
replacing 4 with -(-7) ,  -13 7 2 (new sum is -4)
replacing 2 with -(-4) , -13 7 4 (new sum is -2)
replacing -13 with -(-2) , 2 7 4 (new sum is the first sum i.e 13)

So, such permutations can be counted by storing the frequencies of the common elements of A and b and counting the no of combinations nCr.

But what if -13 is actually an element of B.

Ex:-  A is 7 4 2 
      B is 2 7 4 -13 
 (7,4) (4,2) (7,2) (7,4,2) these will be counted but how will this compatible subsequence be counted.
                            7 4 2 
                            2 4 -13
How can such cases where 'sum of some elements of A are elements of B' be handled?