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";
    }
}