Hôm nay bin9638 làm thơ tình ái tặng người yêu của mình, bài thơ có dạng như sau:

"Anh sẽ why em make poem tình ái

Anh sẽ gom cloud kết thành castle

Vì castle named tình ái

Đón two đứa chúng we mà thôi

Em ơi castle tình ái that

Chắc no yes trên trần gian

Anh take em vào bằng singing

Chắp đôi wing nhung thiên thần"

algorit thấy bin9638 làm thơ quá hay, quá xuất sắc nên cũng học làm theo. Mỗi tội vì mãi code quá nhiều nên bài thơ của cậu chỉ là một xâu kí tự \(S\).

Bây giờ thay vì thơ thì algorit lại nghĩ một vấn đề liên quan đến xâu này. Một xâu con của \(S\) là một đoạn kí tự liên tiếp của nó. Ví dụ xâu TTCC thì có các xâu con là T,C,TT,TC,CC,TTC,TCC,TTCC. Bây giờ bin9638 cần tính giá trị BTS của xâu \(S\), ta có BTS(\(S\))\(= \sum_{st∈S}^{} R(st)*|st|\). Ở đây \(st\) là xâu con của \(S\), \(R(st)\) là số lần xuất hiện của nó trong \(S\), \(|st|\) là độ dài xâu \(st\).

Ví dụ với \(S\)=TTCC thì BTS\((S)\)=\(2 * 1+2*1+1*2+1*2+1*2+1*3+1*3+1*4\)=\(20\).

Input: Một dòng duy nhất là xâu \(S\) gồm các chữ cái latin viết hoa.

Output: Một dòng duy nhất là đáp án.

Ví dụ:

Input:

TTCC

Output:

20

Giới hạn:

• \(30\)% test có |\(S\)| ≤ \(500\).

• \(30\)% test có |\(S\)| ≤ \(2000\).

• \(40\)% test có |\(S\)| ≤ \(500000\).