1class Solution {
2    // Constants for array size and modulo value
3    private static final int MAX_SIZE = 10001;
4    private static final int MOD = (int) 1e9 + 7;
5  
6    // Precomputed factorials and their modular inverses
7    private static final long[] factorials = new long[MAX_SIZE];
8    private static final long[] inverseFactorials = new long[MAX_SIZE];
9
10    // Static block to precompute factorials and their modular inverses
11    static {
12        factorials[0] = 1;
13        inverseFactorials[0] = 1;
14      
15        // Compute factorials modulo MOD
16        for (int i = 1; i < MAX_SIZE; ++i) {
17            factorials[i] = factorials[i - 1] * i % MOD;
18            // Compute modular inverse using Fermat's Little Theorem
19            inverseFactorials[i] = modularPower(factorials[i], MOD - 2, MOD);
20        }
21    }
22
23    /**
24     * Computes (base^exponent) % modulo using fast exponentiation
25     * @param base the base number
26     * @param exponent the power to raise the base to
27     * @param modulo the modulo value
28     * @return (base^exponent) % modulo
29     */
30    public static long modularPower(long base, long exponent, long modulo) {
31        long result = 1;
32      
33        while (exponent != 0) {
34            // If exponent is odd, multiply result by base
35            if ((exponent & 1) == 1) {
36                result = result * base % modulo;
37            }
38            // Square the base and halve the exponent
39            exponent >>= 1;
40            base = base * base % modulo;
41        }
42      
43        return result;
44    }
45
46    /**
47     * Computes the binomial coefficient C(n, k) modulo MOD
48     * @param n total number of items
49     * @param k number of items to choose
50     * @return C(n, k) % MOD
51     */
52    public static long binomialCoefficient(int n, int k) {
53        // C(n, k) = n! / (k! * (n-k)!)
54        return (factorials[n] * inverseFactorials[k] % MOD) * inverseFactorials[n - k] % MOD;
55    }
56
57    /**
58     * Counts the number of good subsequences in the string
59     * A good subsequence has equal frequency for all characters present in it
60     * @param s the input string
61     * @return count of good subsequences modulo MOD
62     */
63    public int countGoodSubsequences(String s) {
64        // Count frequency of each character (26 lowercase letters)
65        int[] charFrequency = new int[26];
66        int maxFrequency = 1;
67      
68        // Calculate character frequencies and find maximum frequency
69        for (int i = 0; i < s.length(); ++i) {
70            int charIndex = s.charAt(i) - 'a';
71            charFrequency[charIndex]++;
72            maxFrequency = Math.max(maxFrequency, charFrequency[charIndex]);
73        }
74      
75        long totalCount = 0;
76      
77        // For each possible frequency k (1 to maxFrequency)
78        for (int targetFreq = 1; targetFreq <= maxFrequency; ++targetFreq) {
79            long subsequenceCount = 1;
80          
81            // For each character, calculate ways to choose targetFreq occurrences
82            for (int charIndex = 0; charIndex < 26; ++charIndex) {
83                if (charFrequency[charIndex] >= targetFreq) {
84                    // Either include this character (choose targetFreq from available)
85                    // or exclude it (multiply by 1, implicit in the +1)
86                    long waysToChoose = binomialCoefficient(charFrequency[charIndex], targetFreq) + 1;
87                    subsequenceCount = subsequenceCount * waysToChoose % MOD;
88                }
89            }
90          
91            // Subtract 1 to exclude the empty subsequence
92            totalCount = (totalCount + subsequenceCount - 1) % MOD;
93        }
94      
95        return (int) totalCount;
96    }
97}
98

1class Solution {
2private:
3    static constexpr int MAX_N = 10001;
4    static constexpr int MOD = 1e9 + 7;
5    static long factorial[10001];
6    static long inverseFactorial[10001];
7  
8    // Fast modular exponentiation: computes (base^exponent) % modulo
9    static long modularPower(long base, long exponent, long modulo) {
10        long result = 1;
11        while (exponent != 0) {
12            // If exponent is odd, multiply result by base
13            if ((exponent & 1) == 1) {
14                result = result * base % modulo;
15            }
16            exponent >>= 1;  // Divide exponent by 2
17            base = base * base % modulo;  // Square the base
18        }
19        return result;
20    }
21  
22    // Static initialization block to precompute factorials and their modular inverses
23    static int initializeFactorials() {
24        factorial[0] = 1;
25        inverseFactorial[0] = 1;
26      
27        // Compute factorials: factorial[i] = i! % MOD
28        for (int i = 1; i < MAX_N; ++i) {
29            factorial[i] = factorial[i - 1] * i % MOD;
30            // Compute modular inverse using Fermat's Little Theorem
31            // Since MOD is prime, inverse of factorial[i] = factorial[i]^(MOD-2) % MOD
32            inverseFactorial[i] = modularPower(factorial[i], MOD - 2, MOD);
33        }
34        return 0;
35    }
36  
37    static int dummy;  // Trigger static initialization
38  
39    // Compute binomial coefficient C(n, k) = n! / (k! * (n-k)!) % MOD
40    static int binomialCoefficient(int n, int k) {
41        return (factorial[n] * inverseFactorial[k] % MOD) * inverseFactorial[n - k] % MOD;
42    }
43  
44public:
45    int countGoodSubsequences(string s) {
46        // Count frequency of each character
47        int charFrequency[26]{};
48        int maxFrequency = 1;
49      
50        for (char& ch : s) {
51            int charIndex = ch - 'a';
52            charFrequency[charIndex]++;
53            maxFrequency = max(maxFrequency, charFrequency[charIndex]);
54        }
55      
56        long totalCount = 0;
57      
58        // For each possible length k (number of times each character appears)
59        for (int k = 1; k <= maxFrequency; ++k) {
60            long waysForCurrentLength = 1;
61          
62            // For each character in the alphabet
63            for (int charIdx = 0; charIdx < 26; ++charIdx) {
64                // If this character appears at least k times in the string
65                if (charFrequency[charIdx] >= k) {
66                    // We can either:
67                    // 1. Not include this character (1 way)
68                    // 2. Choose k occurrences from available occurrences (C(freq, k) ways)
69                    // Total: C(freq, k) + 1 ways
70                    waysForCurrentLength = (waysForCurrentLength * (binomialCoefficient(charFrequency[charIdx], k) + 1)) % MOD;
71                }
72            }
73          
74            // Subtract 1 to exclude the empty subsequence
75            totalCount = (totalCount + waysForCurrentLength - 1) % MOD;
76        }
77      
78        return totalCount;
79    }
80};
81
82// Static member definitions and initialization
83long Solution::factorial[10001];
84long Solution::inverseFactorial[10001];
85int Solution::dummy = Solution::initializeFactorials();
86

1// Constants
2const MAX_N = 10001;
3const MOD = 1000000007;
4
5// Precomputed factorial and inverse factorial arrays
6const factorial: number[] = new Array(MAX_N);
7const inverseFactorial: number[] = new Array(MAX_N);
8
9/**
10 * Fast modular exponentiation: computes (base^exponent) % modulo
11 * Uses binary exponentiation for O(log n) complexity
12 */
13function modularPower(base: number, exponent: number, modulo: number): number {
14    let result = 1;
15    base = base % modulo;
16  
17    while (exponent > 0) {
18        // If exponent is odd, multiply result by base
19        if ((exponent & 1) === 1) {
20            result = (result * base) % modulo;
21        }
22        exponent >>= 1;  // Divide exponent by 2
23        base = (base * base) % modulo;  // Square the base
24    }
25    return result;
26}
27
28/**
29 * Initialize factorials and their modular inverses
30 * Uses Fermat's Little Theorem: a^(p-1) ≡ 1 (mod p) when p is prime
31 * Therefore, a^(-1) ≡ a^(p-2) (mod p)
32 */
33function initializeFactorials(): void {
34    factorial[0] = 1;
35    inverseFactorial[0] = 1;
36  
37    // Compute factorials: factorial[i] = i! % MOD
38    for (let i = 1; i < MAX_N; i++) {
39        factorial[i] = (factorial[i - 1] * i) % MOD;
40        // Compute modular inverse using Fermat's Little Theorem
41        // Since MOD is prime, inverse of factorial[i] = factorial[i]^(MOD-2) % MOD
42        inverseFactorial[i] = modularPower(factorial[i], MOD - 2, MOD);
43    }
44}
45
46// Initialize factorials on module load
47initializeFactorials();
48
49/**
50 * Compute binomial coefficient C(n, k) = n! / (k! * (n-k)!) % MOD
51 * Uses precomputed factorials and their inverses for O(1) calculation
52 */
53function binomialCoefficient(n: number, k: number): number {
54    return (((factorial[n] * inverseFactorial[k]) % MOD) * inverseFactorial[n - k]) % MOD;
55}
56
57/**
58 * Count all good subsequences where each character appears the same number of times
59 * @param s - Input string
60 * @returns Number of good subsequences modulo MOD
61 */
62function countGoodSubsequences(s: string): number {
63    // Count frequency of each character (26 lowercase letters)
64    const charFrequency: number[] = new Array(26).fill(0);
65    let maxFrequency = 1;
66  
67    // Calculate character frequencies and find maximum frequency
68    for (const char of s) {
69        const charIndex = char.charCodeAt(0) - 'a'.charCodeAt(0);
70        charFrequency[charIndex]++;
71        maxFrequency = Math.max(maxFrequency, charFrequency[charIndex]);
72    }
73  
74    let totalCount = 0;
75  
76    // For each possible length k (number of times each character appears in subsequence)
77    for (let k = 1; k <= maxFrequency; k++) {
78        let waysForCurrentLength = 1;
79      
80        // For each character in the alphabet
81        for (let charIdx = 0; charIdx < 26; charIdx++) {
82            // If this character appears at least k times in the string
83            if (charFrequency[charIdx] >= k) {
84                // We can either:
85                // 1. Not include this character in the subsequence (1 way)
86                // 2. Choose exactly k occurrences from available occurrences (C(freq, k) ways)
87                // Total ways: C(freq, k) + 1
88                waysForCurrentLength = (waysForCurrentLength * (binomialCoefficient(charFrequency[charIdx], k) + 1)) % MOD;
89            }
90        }
91      
92        // Subtract 1 to exclude the empty subsequence (when no characters are selected)
93        totalCount = (totalCount + waysForCurrentLength - 1 + MOD) % MOD;
94    }
95  
96    return totalCount;
97}
98