접두접미사

어떤 단어 $w$의 접두접미사란, $w$의 접두사(앞부분)이면서 동시에 접미사(뒷부분)이기도 한 단어 $v$를 말합니다. $w$의 진접두접미사는 비어 있지 않으면서 $w$보다 짧은 접두접미사입니다. $\mathrm{PS}(w)$를 단어 $w$의 진접두접미사의 개수라고 하겠습니다. $w[i, j]$는 $w$에서 $i$번째 위치에서 시작하여 $j$번째 위치에서 끝나는 부분 문자열을 나타내며, 위치는 $1$부터 셉니다.

단어 $w$가 주어졌을 때, $w$의 모든 부분 문자열에 대한 진접두접미사 개수의 총합, 즉 다음 값을 구하세요.

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

입력의 첫 줄이자 유일한 줄에 단어 $w$가 주어집니다. $w$의 길이는 $1 \le |w| \le 10^5$이며, 영어 소문자로만 이루어져 있습니다.

$w$의 모든 부분 문자열에 대한 진접두접미사 개수의 총합을 정수 하나로 출력하세요.