HackerEarth The maximum number problem solution

In this HackerEarth The maximum number problem solution You are given an array A of n elements A1, A2, A3, …,An. Let us define a function F(x) = Sigma(i = 1, n) Ai&x.

Note: Here, & represents bitwise AND operator.

You are required to find the number of different values of x for which F(x) is maximized. There exists a condition for x that it must have exactly l bits sets in its binary representation.

Your task is to find a number of such values for which this function is maximized. Print the required number.

If there are infinite such numbers, then print -1.

It can be proved that under the given constraints the value to be printed is either infinite or not greater than 1e18.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll power(ll x, ll y, ll p) 
{ 
    ll res = 1; 
    x = x % p;  
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1; 
        x = (x*x) % p; 
    } 
    return res; 
} 
ll modInverse(ll n, ll p) 
{ 
    return power(n, p-2, p); 
} 

ll nCrModPFermat(ll n, ll r, ll p) 
{ 
   if (r==0) 
      return 1; 
    ll fac[n+1]; 
    fac[0] = 1; 
    for (int i=1 ; i<=n; i++) 
        fac[i] = fac[i-1]*i%p; 
    return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[n-r], p) % p) % p; 
} 
int main() {
    ll t;
    cin>>t;
    while(t--){
        ll n,k,i,x,y,z;
        ll val=1000000007;
        cin>>n>>k;
        ll a[n];
        for(i=0;i<n;i++){
            cin>>a[i];
        }
        // since k can be atmost 30
        ll bits[31];
        memset(bits,0,sizeof(bits));
        for(i=0;i<n;i++){
            z=0;
            y=a[i];
            while(y!=0){
                if(y%2==1){
                   bits[z]++; 
                }
                z++;
                y/=2;
            }
        }
        x=1;
        for(i=0;i<=30;i++){
            bits[i]*=x;
            x*=2;
        }
        sort(bits,bits+31,greater<int>());
        if(bits[k-1]==0){
            cout<<-1<<endl;
        }
        else{
            x=bits[k-1];
            y=0;
            z=0;
            for(i=0;i<31;i++){
                if(bits[i]==x){
                    y++;
                    if(i<k){
                        z++;
                    }
                }
            }
            cout<<nCrModPFermat(y, z, val)<<endl;
        }
        
    }
    return 0;
}