“जब जब होई धरम की हानी, बाढ़हि असुर अधम अभिमानी। तब-तब धरि प्रभु विविध शरीरा, हरहि दयानिधि सज्जन पीरा।।”

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

long long comb3(long long n) {
    if (n < 3) return 0;
    return ((n * (n - 1) % MOD) * (n - 2) % MOD) / 6 % MOD;
}

int countEvenProductTriplets(const vector<int>& arr) {
    int n = arr.size();
    int odd_count = 0, even_count = 0;
    for (int num : arr) {
        if (num % 2 == 0) {
            even_count++;
        } else {
            odd_count++;
        }
    }

    long long total_triplets = comb3(n);
    long long odd_triplets = comb3(odd_count);

    long long result = (total_triplets - odd_triplets + MOD) % MOD;

    return (int)result;
}

public static long getMinimumCost(int edgeDeviceCost, int inputPeripheralCost, int bundleCost, int x, int y) {
        long minCost = Long.MAX_VALUE;

        for (int bundles = 0; bundles <= Math.max(x, y); bundles++) {
            int remainingEdgeDevices = Math.max(0, x - bundles);
            int remainingPeripherals = Math.max(0, y - bundles);

            long cost = (long) bundles * bundleCost
                    + (long) remainingEdgeDevices * edgeDeviceCost
                    + (long) remainingPeripherals * inputPeripheralCost;

            minCost = Math.min(minCost, cost);
        }

        return minCost;
    }

static final int MOD = (int)1e9 + 7;

    public static int countGoodSubsequences(String word) {
        int[] freq = new int[26];
        int maxFreq = 0;
        for (char c : word.toCharArray()) {
            freq[c - 'a']++;
            maxFreq = Math.max(maxFreq, freq[c - 'a']);
        }

        int n = word.length();
        long[] factorial = new long[maxFreq + 1];
        long[] invFactorial = new long[maxFreq + 1];
        factorial[0] = invFactorial[0] = 1;

        for (int i = 1; i <= maxFreq; i++) {
            factorial[i] = factorial[i - 1] * i % MOD;
        }

        invFactorial[maxFreq] = modInverse(factorial[maxFreq], MOD);
        for (int i = maxFreq - 1; i >= 1; i--) {
            invFactorial[i] = invFactorial[i + 1] * (i + 1) % MOD;
        }

        long totalGoodSequences = 0;

        for (int k = 1; k <= maxFreq; k++) {
            long total_k = 1;
            boolean hasValidChar = false;
            for (int i = 0; i < 26; i++) {
                if (freq[i] >= k) {
                    hasValidChar = true;
                    long c = comb(freq[i], k, factorial, invFactorial);
                    total_k = total_k * (c + 1) % MOD;
                }
            }
            if (hasValidChar) {
                total_k = (total_k - 1 + MOD) % MOD;
                totalGoodSequences = (totalGoodSequences + total_k) % MOD;
            }
        }

        return (int) totalGoodSequences;
    }

    static long modInverse(long a, int mod) {
        return modPow(a, mod - 2, mod);
    }

    static long modPow(long a, long b, int mod) {
        long result = 1;
        a %= mod;
        while (b > 0) {
            if ((b & 1) == 1)
                result = result * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return result;
    }

    static long comb(int n, int k, long[] factorial, long[] invFactorial) {
        if (k > n) return 0;
        return factorial[n] * invFactorial[k] % MOD * invFactorial[n - k] % MOD;
    }

#include <bits/stdc++.h>
using namespace std;

string getPerfectExecutionString(string& category) {
    vector<int> freq(26, 0);
    for (char& x : category) {
        freq[x - 'a']++;
    }

    string temp;
    string ans; 
    int p = 0;  

    for (int i = 0; i < 26; i++) {
        while (!temp.empty() && temp.back() - 'a' <= i) {
            ans.push_back(temp.back());
            temp.pop_back();
        }

        while (freq[i]) {
            if (category[p] - 'a' == i) {
                ans.push_back(category[p]);
            } else {
                temp.push_back(category[p]); 
            }
            freq[category[p++] - 'a']--;
        }
    }

    while (!temp.empty()) {
        ans.push_back(temp.back());
        temp.pop_back();
    }

    return ans;
}