Một xâu con được gọi là đặc biệt nếu tất cả kí tự xuất hiện trong xâu gốc đều xuất hiện trong xâu con với số lần là bằng nhau.

Nhiệm vụ của bạn là đếm số lượng xâu con đặc biệt của xâu đã cho.

Input

• Dòng đầu vào duy nhất có một xâu độ dài \(n\). Tất cả các kí tự nằm giữa a\(\dots\)z.

Output

• In một số nguyên: số lượng xâu con đặc biệt.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)

Example

Sample input

abccabab

Sample output

5

Note

Các xâu con đặc biệt là: abc, cab, abccab, bccaba và ccabab.