AT_abc295_d [ABC295D] Three Days Ago

[problemUrl]: https://atcoder.jp/contests/abc295/tasks/abc295_d `20230322` は並べ替えると `02320232` となり、これは `0232` を $ 2 $ 度繰り返しています。 このように、数字のみからなる文字列であって、適切に文字を並び替える (そのままでもよい) ことによって同じ列を $ 2 $ 度繰り返すようにできるものを **嬉しい列** と呼びます。 数字のみからなる文字列 $ S $ が与えられるので、以下の条件を全て満たす整数の組 $ (l,r) $ はいくつあるか求めてください。 - $ 1\ \le\ l\ \le\ r\ \le\ |S| $ ( $ |S| $ は $ S $ の長さ) - $ S $ の $ l $ 文字目から $ r $ 文字目までの (連続する) 部分文字列は嬉しい列である。

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

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

### 制約 - $ S $ は数字のみからなる長さ $ 1 $ 以上 $ 5\ \times\ 10^5 $ 以下の文字列 ### Sample Explanation 1 $ S= $ `20230322` です。 条件を満たす整数組 $ (l,r) $ は $ (1,6),(1,8),(2,7),(7,8) $ の $ 4 $ つです。 ### Sample Explanation 2 $ S $ の先頭が `0` である場合もあります。