Palindromic Substring

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

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

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

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

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

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

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

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

3
aba

13

aba の空でない連続部分文字列は a、b、a、ab、ba、aba の つです。

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

以上より、答えは です。

5
wakka

55

17
ushitapunichiakun

969

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