U334271 公司（Company）

你是蔡老板公司的一个打工仔。现在蔡老板需要给公司取一个名字，他选定了一个串 $S$，并且决定这个名字将是串 $S$ 的某一个非空子串，不过他还没有确定具体选择哪个子串。

蔡老板认为一个串是好的，当且仅当存在一种方式，把每个字符改成 (和)，使得它形成一个合法的括号序列，并且满足每一对匹配的括号所对应的字符相同，如 ```aabaab``` 可以对应成 ```()(())```，但不能对应成 ```((()))```。\ 合法的括号序列定义为： 1. 空序列是合法的括号序列 2. 如果 $A$ 和 $B$ 是合法的括号序列，则 $(A)$ 和 $AB$ 都是合法的括号序列。 蔡老板想知道有多少个 $S$ 的非空子串是好的，这里出现位置不同算作不同的子串。你作为打工仔，如果能告诉蔡老板正确的答案，蔡老板就会给你加薪。

一行包含一个只有小写字母组成的字符串 $S$。

输出一行表示有多少种好的子串。

样例1：有 $aa,bb,aabb$ 和 $abba$ 四个好的子串。 对于所有测试点 $|S| \leq 10 ^ 6$。\ 对于 $20\%$ 的测试点满足 $|S| \leq 10$。\ 对于 $40\%$ 的测试点满足 $|S| \leq 200$。\ 对于 $70\%$ 的测试点满足 $|S| \leq 5000$。