Prefix-Suffixes

A prefix-suffix (a border) of a word $w$ is a word $v$ that is both a prefix (an initial fragment) and a suffix (a final fragment) of $w$. A proper prefix-suffix of $w$ is any prefix-suffix that is non-empty and strictly shorter than $w$. Let $\mathrm{PS}(w)$ denote the number of proper prefix-suffixes of $w$. Let $w[i, j]$ denote the substring of $w$ that starts at position $i$ and ends at position $j$; positions are numbered from $1$.

Given a word $w$, compute the total number of proper prefix-suffixes over all substrings of $w$, that is

$\sum_{1 \le i \le j \le |w|} \mathrm{PS}(w[i, j])$

The first and only line of input contains the word $w$. Its length satisfies $1 \le |w| \le 10^5$, and it consists only of lowercase English letters.

Print a single integer: the total number of proper prefix-suffixes over all substrings of $w$.