Prefix or Suffix

問題文

長さ $N$ の文字列 $S$ が与えられます。

文字列 $T$ のスコアを以下のように定義します。

• $T$ のあるPrefixまたはSuffixと一致するような空でない文字列の種類数

例えば aba のPrefixまたはSuffixと一致するような空でない文字列は以下の $4$ 種類であるため、aba のスコアは $4$ です。

• a, ab, ba, aba

$S$ の連続部分文字列は $N(N+1)/2$ 個ありますが、それらのスコアの総和を求めてください。

制約

• $1 \le N \le 10^5$
• $S$ は英小文字からなる長さ $N$ の文字列である。

入力

出力

計算結果を一行に出力してください。

サンプル1

3
aba

13

連続部分文字列とそのスコアは以下の通りです。

• a：$1$
• b：$1$
• a：$1$
• ab：$3$
• ba：$3$
• aba：$4$

サンプル2

4
aaaa

20

サンプル3

13
bacbabcabcaca

787