Untitled

class Solution {
public:
    const int MOD = 1e9 + 7;

      int arr[100001];
      int ct [100001];
    
     void primescore(){
         memset(ct, 0, sizeof(ct));
         for(int i=1; i<=100000; i++){
             arr[i]=i;
         }
         ct[1]=0;
         for (int i = 2; i <= 100000; ++i) {
        if (arr[i]!= 1) {
            for (int j = i; j <=100000; j += i) {
               while(arr[j]%i==0){
                   arr[j]=arr[j]/i;
               }
                ct[j]++;
            }
        }
    }
            
     }
    
    long long binaryExponentiation(long long n, long long m) {
    long long result = 1;
    n %= MOD; 
    while (m > 0) {
        if (m % 2 == 1) {
            result = (result * n) % MOD;
        }
        n = (n * n) % MOD;
        m /= 2; 
    }
    return result;
}




    
    int maximumScore(vector<int>& prisco, int k) {
        
         primescore();
        
        int n =prisco.size();
        vector<int>nums;
        for(int i=0; i<n; i++){
            nums.push_back(ct[prisco[i]]);
        }
        
        vector<int>left, right;
        stack<int>st;
        
        for(int i=0; i<n; i++){
           while(st.size() && nums[st.top()]<nums[i]){
               st.pop();
           } 
            if(st.size()==0){
                left.push_back(-1);
            }else {
                left.push_back(st.top());
            }
            st.push(i);
        }
         while(st.size())st.pop();
         for(int i=n-1; i>=0; i--){
           while(st.size() && nums[st.top()]<=nums[i]){
               st.pop();
           } 
            if(st.size()==0){
                right.push_back(n);
            }else {
                right.push_back(st.top());
            }
            st.push(i);
        }
        reverse(right.begin(), right.end());
         while(st.size())st.pop();
//         for(int i=0; i<n; i++){
//             cout<<left[i]<<" ";
//         }
//         cout<<endl;
//         for(int j=0; j<n; j++){
//             cout<<right[j]<<" ";
//         }
//         cout<<endl;
        
        vector<int>final;
        for(int i=0; i<n; i++){
            final.push_back((right[i]-i)*(i-left[i]));
            // cout<<final[i]<<" ";
        }
        priority_queue<pair<int, int>>pq;
        
        for(int i=0; i<n; i++){
            pq.push({prisco[i],final[i]});
        }
          // cout<<endl;
        long long ans=1;
        while(k){
            pair<int, int>front = pq.top(); pq.pop();
             // cout<<front.first<<" "<<front.second<<endl;
            if(front.second<=k){
            ans= (ans* binaryExponentiation(front.first, front.second))%MOD;
                k=k-front.second;
            }else{
             ans= (ans* binaryExponentiation(front.first, k))%MOD;
               k=0;                
            }
            
        }
        return ans;
      
        return 0;
    }
};