题目描述

字符串 20230322 可以被排列为 02320232, 这是字符串 0232 重复两次。

类似地，我们称一个由数字（0，1，2，……，9）构成的字符串是​快乐的​，如果可以把它排列成另一个字符串重复两次的样子。

给你一个由数字构成的字符串 $S$。求出有多少对整数 $(l, r)$ 满足下列条件。

• $1 \le l \le r \le |S|$。（$|S|$ 是 $S$ 的长度。）
• 由 $S$ 的第 $l$ 个到第 $r$ 个字符构成的串是​快乐的​。

输入格式

输入一个字符串S

输出格式

输出合法的方案数

20230322

4

0112223333444445555556666666777777778888888889999999999

185

提示

$1 \le |S| \le 5 * 10^{6}$