We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Beautiful Strings

Beautiful Strings

You are given a string, , consisting of lowercase English letters.

A string is beautiful with respect to if it can be derived from by removing exactly characters.

Find and print the number of different strings that are beautiful with respect to .

Input Format

A single string of lowercase English letters denoting .

Constraints

  • holds for test cases worth at least of the problem's score.
  • holds for test cases worth at least of the problem's score.

Output Format

Print the number of different strings that are beautiful with respect to .

Sample Input

abba

Sample Output

4

Explanation

The following strings can be derived by removing characters from : .

This gives us our set of unique beautiful strings, . As , we print .