公司（company）

时间:1s 空间256MB

题目背景

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

题目描述

蔡老板认为一个串是好的，当且仅当存在一种方式，把每个字符改成 (和)，使得它形成一个合法的括号序列，并且满足每一对匹配的括号所对应的字符相同，如 aabaab 可以对应成 ()(())，但不能对应成 ((()))。 合法的括号序列定义为：

1. 空序列是合法的括号序列
2. 如果 $A$ 和 $B$ 是合法的括号序列，则 $(A)$ 、$(B)$和 $AB$ 都是合法的括号序列。

蔡老板想知道有多少个 $S$ 的非空子串是好的，这里出现位置不同算作不同的子串。你作为打工仔，如果能告诉蔡老板正确的答案，蔡老板就会给你加薪。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

aabbab

样例输出 #1

4

样例 #2

样例输入 #2

aaaaaaaaaa

样例输出 #2

25

提示

样例1：有 $aa,bb,aabb$ 和 $abba$ 四个好的子串。

对于所有测试点 $|S| \leq 10 ^ 6$。 对于 $20\%$ 的测试点满足 $|S| \leq 10$。 对于 $40\%$ 的测试点满足 $|S| \leq 200$。 对于 $70\%$ 的测试点满足 $|S| \leq 5000$。