配点 : $400$ 点

問題文

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$

出力

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

20230322

4

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

0112223333444445555556666666777777778888888889999999999

185

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

3141592653589793238462643383279502884197169399375105820974944

9