P4248 [AHOI2013] Difference

Given a string $S$ of length $n$, let $T_i$ denote the suffix starting from its $i$-th character. Compute $$\displaystyle \sum_{1\leqslant i

One line, a string $S$.

One line, an integer representing the required value.

#### Constraints - For $100\%$ of the testdata, it is guaranteed that $2\le n\le 500000$, and all characters in $S$ are lowercase letters. Translated by ChatGPT 5