字符串 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$ 之间（包含边界）。