Ta định nghĩa một xâu Chí Bảo là một xâu thỏa mãn hai điều kiện sau:

• Chỉ chứa các ký tự chữ số như 0, 1,, 2,..., 9.
• Có thể xáo trộn các ký tự lại thành hình thái của một cặp xâu kề nhau và giống nhau. Ví dụ: 52902095 có thể được xáo trộn lại thành 29052905 - thể hiện hình thái của cặp xâu 2905 kề nhau.

Cho một xâu \(S\) chỉ gồm các ký tự chữ số, bạn hãy lập trình tính toán xem có bao nhiêu xâu con của \(S\) là một xâu Chí Bảo. Một xâu con của \(S\) được định nghĩa là chuỗi các ký tự liên tiếp từ \(S_l\) đến \(S_r\) sao cho \(1 \leq l \leq r\leq |S|\).

Input

Một dòng duy nhất chứa xâu \(S\) có độ dài không vượt quá \(5\cdot 10^5\).

Output

Một số nguyên duy nhất là kết quả của bài toán (số lượng xâu con của \(S\) là xâu Chí Bảo).

Ví dụ

Sample input 1

52902095

Sample output 1

2

Giải thích

Các xâu con thỏa mãn là 290209 và 52902095.

Sample input 2

0113335555777772222226666666444444448888888889999999999

Sample output 2

185

Giải thích

\(S\) có thể bắt đầu bằng ký tự `0

Sample input 3

5772156649

Sample output 3

2