You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

字符串 26362662 可以重新排列成 26626623，这是 266 重复两次的形式。类似地，当一个由数字组成的字符串可以重新排列成某个字符串的重复两次（或已经是这种形式），我们称这个字符串是 "快乐的"。

给定一个由数字组成的字符串 S，找到满足以下所有条件的整数对 (l, r) 的数量：

1. $1 \leq l \leq r \leq |S|$ （$|S|$ 是字符串 S 的长度）
2. 从 S 的第 $l$ 个字符到第 $r$ 个字符形成的（连续的）子字符串是快乐的

输入格式

一行，包括一个字符串 $S$

输出格式

输出一个整数，表示满足条件的 (l, r) 对的数量。

20230322

4

我们有 $S=20230322$。

以下是满足条件的四个整数对： (1,6), (1,8), (2,7), 和 (7,8)。

0112223333444445555556666666777777778888888889999999999

185

3141592653589793238462643383279502884197169399375105820974944

9

提示

S 是一个由数字组成的字符串，长度在 $1$ 到 $5 \times 10^5$ 之间（包含边界）。