問題文


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

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

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

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

  • a, ab, ba, aba

の連続部分文字列は 個ありますが、それらのスコアの総和を求めてください。

制約


  • は英小文字からなる長さ の文字列である。

入力



出力


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

サンプル1


入力1
3
aba
出力1
13

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

  • a
  • b
  • a
  • ab
  • ba
  • aba

サンプル2


入力2
4
aaaa
出力2
20

サンプル3


入力3
13
bacbabcabcaca
出力3
787

提出


Go (1.14)