Tập phân biệt

Cho xâu ký tự \(S\) bao gồm các chữ cái trong bảng chữ cái Latin viết thường (tức là các ký tự từ 'a' đến 'z). Trong xâu này, \(S_{i}\) là ký tự ở vị trí thứ \(i\) (tính từ \(1\)). Ta định nghĩa một xâu con liên tiếp của \(S\), ký hiệu là , là một đoạn liên tục trong \(S\) bắt đầu từ vị trí thứ \(l\) đến vị trí thứ \(r\). Xâu con này bao gồm các ký tự \(S_{l}S_{l + 1}...S_{r}\) theo đúng thứ tự như trong \(S\). Lưu ý: Xâu rỗng là xâu con của \(S\).

Với mỗi xâu con liên tiếp \(S[l...r]\), ta định nghĩa \(P(S[l...r])\) là tập hợp các ký tự khác nhau xuất hiện trong đoạn từ \(l\) đến \(r\) của xâu \(S\).
Ví dụ: Với \(S = abacacb\), ta có:

• \(S[1..2] = aba\), \(P(S[1...2]) = {a, b}\)
• \(S[4. .5] = ca\), \(P(S[4...5]) = {a, b}\)
• \(S[2. .7] = bacacb\), \(P(S[2...7] = {a, b, c}\)

Yêu cầu: Trong tất cả các xâu con liên tiếp của \(S\), hãy tính số tập \(P(S[l...r])\) phân biệt.

Input

Một dòng duy nhất chứa xâu \(S\) \((|S| \leq 10^6)\). Dữ liệu đảm bảo \(S\) chỉ gồm các ký tự tiếng Anh in thường.

Output

Một số nguyên duy nhất là số tập \(P\) phân biệt tìm được.

Example

abacacb

8

Scoring

• Có \(25\%\) số điểm của bài với \(n \leq 500\)
• Có \(25\%\) số điểm khác với \(n \leq 5000\)
• Có \(25\%\) số điểm khác thỏa mãn \(n \leq 50000\)
• Còn lại không có điều kiện gi thêm