Magical Substrings

Given a string \(S\) of length \(n\). Let \(S\) contain exactly \(k\) distinct characters. A substring is defined as a contiguous segment of \(S\). A magical substring is a non-empty substring of \(S\) that satisfies the following conditions:

1. The substring contains exactly \(k\) distinct characters.
2. Each character in the substring appears the same number of times.

Two substrings are considered different if their starting or ending indices are different. Your task is to count the number of magical substrings in \(S\).

Note: The frequency of each character in a magical substring must be identical. In particular, if each character appears \(t\) times, then the length of the substring is \(t \cdot k\).

inputFormat

The input consists of a single line containing the string \(S\).

\(S\) is a non-empty string.

outputFormat

Output a single integer, the number of magical substrings in \(S\).

sample

abab

4