### 问题描述 鑫鑫和柔柔是一对好朋友，她们在参加一个叫做“数字对对碰”的抽奖活动。 参与者每次将抽取一个字符串，当且仅当它可以被重排后分成两段，每一段都是一个相同的子串时，视为中将。例如，抽取到字符串 `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` 组成。