给你一个字符串 $$$s$$$。如果有一个(可能是空的)链接字符串 $$$c$$$ 满足以下条件,则其一对非空子字符串 $$$(a, b)$$$ 被称为纠缠:
- $$$s$$$ 中每次出现 $$$a$$$ 后紧跟着 $$$cb$$$;
- $$$s$$$ 中每次出现 $$$b$$$ 之前都紧接着 $$$ac$$$。
换句话说,$$$a$$$ 和 $$$b$$$ 仅作为 $$$acb$$$ 的子字符串出现在 $$$s$$$ 中。计算 $$$s$$$ 的纠缠子串对总数。
字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。
输入
第一行也是唯一一行包含小写英文字母的字符串 $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$) — 您应该计算纠缠子字符串对的字符串。
输出
输出单个整数,$$$s$$$ 的纠缠子串对的数量。
示例
输入 #1
abba
输出 #1
1
输入 #2
abacaba
输出 #2
0
输入 #3
abcabcabcabc
输出 #3
5
输入#4
adamant
输出#4
82
注意
在第一个示例中,唯一的纠缠对是 (ab,ba)。对于这一对,相应的链接字符串 $$$c$$$ 为空,因为它们仅作为整个字符串 abba 的子字符串出现,而整个字符串 abba 之间没有任何字符。
在第二个示例中,没有纠缠对。
在第三个示例中,纠缠对是 (a,b)、(b,c)、(a,c)、(a,bc) 和 (ab,c)。对于大多数对,相应的链接字符串 $$$c$$$ 为空,但对 (a,c) 除外,其链接字符串 $$$c$$$ 为 b,因为 a 和 c 仅作为字符串 abc 的子字符串出现。