题目描述

字符串 20230322 可以重排为 02320232，这个字符串是 0232 的两次重复。
类似地，如果一个由数字组成的字符串可以重排为（或已经是）某个字符串的两次重复，则称其为快乐字符串。
给定一个由数字组成的字符串 $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)$。

示例输入 2

0112223333444445555556666666777777778888888889999999999

示例输出 2

185

$S$ 可能以 0 开头。

示例输入 3

3141592653589793238462643383279502884197169399375105820974944

示例输出 3

9