問題文

20230322 は並べ替えると 02320232 となり、これは 0232 を $2$ 度繰り返しています。
このように、数字のみからなる文字列であって、適切に文字を並び替える (そのままでもよい) ことによって同じ列を $2$ 度繰り返すようにできるものを 嬉しい列 と呼びます。
数字のみからなる文字列 $S$ が与えられるので、以下の条件を全て満たす整数の組 $(l,r)$ はいくつあるか求めてください。

• $1 \\le l \\le r \\le |S|$ ( $|S|$ は $S$ の長さ)
• $S$ の $l$ 文字目から $r$ 文字目までの (連続する) 部分文字列は嬉しい列である。

制約

• $S$ は数字のみからなる長さ $1$ 以上 $5 \\times 10^5$ 以下の文字列

入力

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

$S$

出力

答えを整数として出力せよ。

入力例 1

20230322

出力例 1

4

$S=$ 20230322 です。
条件を満たす整数組 $(l,r)$ は $(1,6),(1,8),(2,7),(7,8)$ の $4$ つです。

入力例 2

0112223333444445555556666666777777778888888889999999999

出力例 2

185

$S$ の先頭が 0 である場合もあります。

入力例 3

3141592653589793238462643383279502884197169399375105820974944

出力例 3

9