1902 - ABA

時間制限 1 秒 / メモリ制限 64 MB / 得点 30 / Writer DAI_0110 / x 1 / 統計 /


TLE
1sec
MLE
64MB
得点
30

問題

英大文字小文字からなる文字列 $S$ が与えられます。
整数の組 (i,j,k) であって、以下の条件をともに満たすものの個数を求めてください。

  • $1 \leq i < j < k \leq |S|$
  • $S_i,S_j,S_k $をこの順に結合して得られる長さ3の文字列が回文となる

ただし、$|S| $は文字列$S$の長さ、$S_x$は$S$の$x$番目の文字を指します

入力

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

$S$

1行目に文字列$S$が与えられる。

出力

答えを出力し最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

  • $S$は長さ$1$以上$2 \times 10^5 $以下の英大文字小文字からなる文字列

入出力例

入力例1

ABCACC

出力例1

5

$(i,j,k) = (1,2,4),(1,3,4),(3,4,5),(3,4,6),(3,5,6)$が条件を満たします。

入力例2

OOOOOOOO

出力例2

56

入力例3

XYYXYYXYXXX

出力例3

75