問題

英小文字(a, b, c, ..., z)からなる長さ $N$ の文字列 $S$ が与えられます。以下の条件を全て満たす $(i, j)$ の組の数を求めてください。

• $i, j$ はともに正の整数
• $i \leq j \leq N$
• 任意の $(j - i)$ 以下の非負整数 $k$ について、$S$ の $(i + k)$ 文字目と $(j - k)$ 文字目が一致する

制約

• $1 \leq N \leq 10^6$

入力

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

サンプル

abcba

7

aaaaa

15