Count the Number of Good Subsequences

Try to solve the Count the Number of Good Subsequences problem.

Statement

Count and return the number of good subsequences in the given string s. You may return the modulo 109+710^9 + 7 of the count.

  • A subsequence is a sequence formed from another sequence by deleting some or no elements while keeping the order of the remaining elements unchanged.

  • A good subsequence is a subsequence of a string if it is not empty and the frequency of each character is the same.

Constraints:

  • 1≤1 \leqs.length ≤104\leq 10^4

  • s will only contain lowercase English characters.

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.