小文字からなる文字列 $s$ が与えられます。その長さを $|s|$、逆順にした文字列を $s^R$（$s$ の左右を反転して得られる文字列）と表します。また、$\operatorname{prefix}(s, i)$ は $s$ の先頭 $i$ 文字からなる部分文字列、$\operatorname{suffix}(s, i)$ は $s$ の末尾 $i$ 文字からなる部分文字列を表します。

これに基づき、文字列 $s$ の $\operatorname{Porder}$ の値を、次の条件を満たす最大の整数 $i$ と定義します：$$\operatorname{prefix}(s, i) = (\operatorname{suffix}(s, i))^R$$ ここで $0 \le i \le |s|$ です。特に、この条件を満たす正の整数が存在しない場合、$\operatorname{Porder}$ の値は $0$ です。

文字列 $s$ の部分文字列は、$l$ 番目の文字から $r$ 番目の文字までの連続した文字列として定義されます。添字は $1$ から始まり、$1 \le l \le r \le |s|$ を満たします。

文字列 $s$ の すべての部分文字列 の $\operatorname{Porder}$ の値の総和を求めてください。

入力

入力は $1$ 行で、文字列 $s$ $(1 \le |s| \le 10^5)$ が与えられます。文字列は小文字のみからなることが保証されます。

出力

$s$ のすべての部分文字列の $\operatorname{Porder}$ の値の総和を表す整数を $1$ 行に出力してください。

入出力例

入力 1

aa

出力 1

4

入力 2

abcdba

出力 2

9

注記

入出力例 2 を例にすると：

• $\operatorname{Porder}$ の値が $2$ である部分文字列は abcdba です（合計 $1$ 個）。

• $\operatorname{Porder}$ の値が $1$ である部分文字列は bcdb と、長さ $1$ のすべての部分文字列です（合計 $7$ 個）。

• 残りの部分文字列の $\operatorname{Porder}$ の値はすべて $0$ です。

したがって、すべての部分文字列の $\operatorname{Porder}$ の値の総和は $1 \times 2 + 7 \times 1 + 0 = 9$ です。