### 问题描述 小蓝和小桥是一对好朋友，他们经常一起玩各种游戏。今天，他们在玩一个叫做“快乐字符串”的游戏。 一个字符串被称为“快乐字符串”，当且仅当它可以被重排后分成两段，每一段都是一个相同的子串。例如，字符串 `06010061` 可以重排成 `06010601`，它是由两个 `0601` 组成的。 小蓝给了小桥一个字符串 $S$，由数字组成。现在，小桥想知道有多少对整数 $(l,r)$ 满足以下条件： - $1 \leq l \leq r \leq|S|$（$|S|$ 是 $S$ 的长度）。 - 由 $S$ 第 $l$ 到第 $r$ 个字符组成的子串是“快乐字符串”。 请你帮助小桥解决这个问题。 ### 输入格式 一个字符串 $S$，由数字 $0\sim 9$ 组成，长度在 $1$ 到 $10^5$ 之间。 ### 输出格式 一个整数，表示满足条件的整数对 $(l,r)$ 的个数。 ### 样例输入 ``` 06010061 ``` ### 样例输出 ``` 2 ``` ### 说明 样例中，共有两个满足条件的整数对 $(l,r)$： - 当 $l=1,r=8$ 时，子串为 `06010061`，可以被重排成 `06010601`，它由两个 `0601` 组成。 - 当 $l=5,r=6$ 时，子串为 `00`，它可以由两个 `0` 组成。