Tổng đếm xâu con

Cho xâu $s$ chỉ gồm các chữ cái Latin thường. Với mỗi cặp $(l,r)$ thỏa mãn $1\le l\le r\le |s|$, ta gọi $s[l..r]$ là xâu con của $s$ bắt đầu ở vị trí $l$ và kết thúc ở vị trí $r$ (bao gồm hai đầu).

Với hai xâu $x$ và $y$, định nghĩa hàm $F(x,y)$ như sau: tìm danh sách tất cả các cặp $(l,r)$ sao cho $x[l..r]=y$, sắp xếp danh sách theo $l$ tăng dần. Giá trị của $F(x,y)$ bằng số dãy con liên tiếp khác rỗng của danh sách này.

Ví dụ, với $x=$ babbabbababbab và $y=$ babb, danh sách các cặp là $(1,4),(4,7),(9,12)$, có $6$ dãy con liên tiếp khác rỗng nên $F(x,y)=6$.

Nhiệm vụ của bạn: với xâu $s$ cho trước, hãy tính tổng $F(s,x)$ trên tất cả các xâu $x$ thuộc tập các xâu con của $s$ (mỗi xâu con phân biệt được tính đúng một lần).

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ gồm các chữ cái Latin thường.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng cần tìm.

Ràng buộc

• $1\le |s|\le {10}^5$.

Ví dụ