Consider a string s of length n consisting of characters 0 to 9. Let $r(s)$ be the number of distinct characters this string has, and $N(c)$ be the number of times character c appears in the string. We call the string s happy if $N(0) \lt \frac{n}{r(s)}$

For example strings $010$ and $012$ are NOT happy, but strings $0112$ and $123456789$ are happy.

Given a string S, find the number of happy substrings(out of a total $\frac{|S|(|S|+1)}{2}$ ) of S.

Input
The only line of the input contains the string S

Output
Print one line containing the number of happy substrings of S

Constraints

• $|S| \le 10^5$