問題
英大文字小文字からなる文字列 $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