Untitled

MOD = 10 ** 9 + 7


class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
        f = Counter(s)
        if k > len(f):
            return 0
        threshold = sorted(f.values(), reverse=True)[k - 1]
        f = list(f.values())
        @cache
        def count(i, k):
            if i == len(f):
                return 1 if k == 0 else 0
            res = 0 if f[i] > threshold else count(i + 1, k)
            if f[i] >= threshold:
                res += count(i + 1, k - 1) * f[i] % MOD
                res %= MOD
            return res
        return count(0, k)