Palindromic Substring

2 secs 1024 MB
bayashiko

問題文


長さが の英小文字からなる文字列 が与えられます。

の空でない連続部分文字列 として考えられるもの全てについて以下の値を求め、それらの総和を答えてください。

  • の空でない連続部分文字列のうち、回文であるものの長さの総和

ただし、各連続部分文字列について、文字列として等しくても取り出した位置が異なるならば区別します。

また、答えは非常に大きくなることがあるので、答えを で割った余りを出力してください。

  

制約


  • は英小文字からなる
  • は整数

  

入力


入力は以下の形式で標準入力から与えられます。


  

出力


答えを出力してください。

  

入力例1


3
aba

出力例1


13

aba の空でない連続部分文字列は abaabbaaba つです。

a の空でない連続部分文字列のうち回文であるものは a つで、長さの総和は です。
b の空でない連続部分文字列のうち回文であるものは b つで、長さの総和は です。
a の空でない連続部分文字列のうち回文であるものは a つで、長さの総和は です。
ab の空でない連続部分文字列のうち回文であるものは ab つで、長さの総和は です。
ba の空でない連続部分文字列のうち回文であるものは ba つで、長さの総和は です。
aba の空でない連続部分文字列のうち回文であるものは abaaba つで、長さの総和は です。

以上より、答えは です。

入力例2


5
wakka

出力例2


55

入力例3


17
ushitapunichiakun

出力例3


969

ここにそのようなケースを置くことは出来ませんが、答えは非常に大きくなることがあるので で割った余りを出力することに注意してください。

Submit


Go (1.14)