class Solution {
public:
    int maximumProduct(vector<int>& nums, int k) {
        priority_queue<long long int,vector<long long int>,greater<long long int>>pq;
        unordered_map<long long int,long long int>mp;
        
        for(int i=0;i<nums.size();i++)mp[nums[i]]++;
        
        for(auto x : mp)pq.push(x.first);
        
        while(k>0){
         
            int val=pq.top();
            if(mp[val+1]==0)pq.push(val+1);
            if(mp[val]<=k){
                
                mp[val+1]+=mp[val];
                k-=mp[val];
                mp[val]=0;
            }
            else {
                mp[val+1]+=k;
                mp[val]-=k;
                k=0;
            }
            if(mp[val]==0)pq.pop();
           // if(mp[val+1]==1)pq.push(val+1);
        }
        long long int ans=1;
        long long int mod=1e9+7;
        while(!pq.empty()){
           // cout<<pq.top()<<" "<<mp[pq.top()]<<endl;
        //   long long int cur=pow(pq.top(),mp[pq.top()]); (this will give run time error)
            int num=mp[pq.top()];
            int cur=1;
            for(int i=0;i<num;i++){
                cur=((cur%mod)*(pq.top()%mod))%mod;
            }
            ans=(ans%mod * cur%mod)%mod;
            pq.pop();
        }
        return ans%mod;
    }
};