Problem 2F. 括号的匹配

时间限制：1s

空间限制：256MB

Description

我们在学习栈的时候都做过括号的匹配，知道了括号的匹配需要满足以下条件：

1、总体上看，左括号和右括号必须数量一样多。

2、从左到右依次看，任何时候右括号不能多于左括号

当然我们并不总是一眼能看出括号的添加是否正确。所以我们总是需要编写程序检查括号匹配是否正确。

---

现在我们将这个问题进一步研究，首先我们更加正式地定义括号序列：

仅由括号 \('('\) 和 \(')'\) 组成的字符串称为括号序列。当然下面这些条件也将满足：

• 空字符串是一个正确的括号序列。
• 如果序列 \(s\) 是一个正确的括号序列，那么 \((s)\) 也是一个正确的括号序列。
• 如果 \(s\) 和 \(t\) 是正确的括号序列，那么 \(st\) ( \(s\) 和 \(t\) 首尾连接 ) 也是正确的括号序列。

---

对于一个仅含有 \('('\) ， \(')'\) 和 字符 \('?'\) 的新字符序列 \(s\) ，我们可以对其某段子序列 \([s_l, s_r]\ (1 \le l \le r \le s_{len})\) 进行如下操作：

• 将该段字符串中的任意字符 \('?'\) 替换成为 \('('\) 或 \(')'\) 。

若存在当且仅当一种方法可以将每个问号替换为 \('('\) 或 \(')'\) ，从而得到的新字符串是正确匹配的非空括号序列，那么这个子序列 \([s_l, s_r]\ (1 \le l \le r \le s_{len})\) 被称为是唯一匹配序列。

那么对于整个字符串 \(s\) ，有多少个整数对 \([l,r]\ (1 \le l \le r \le s_{len})\) 对应的子序列 \([s_l, s_r]\) 是唯一匹配序列？

Input Format

输入一行一个字符串 \(s\)，只由字符 \('('\) 、\(')'\) 和 \('?'\) \((2 ≤ |s| ≤ 5000)\) 组成。

Output Format

输出一行一个整数，含义见上文。

Input Example #1：

((?))

Output Example #1：

4

Input Example #2：

??()??

Output Example #2：

7

Note

对于第一个测试用例，\(s\) 的唯一匹配序列是：

1. "(?" 可以转换为 "()" 。
2. "?)" 可转换为"()" 。
3. "((?)" 可转换为"(())" 。
4. "(?))" 可转换为"(())" 。

对于第二个测试用例，\(s\) 的唯一匹配序列是：

1. "??" 可以转换为"()" 。
2. "()" 。
3. "??()" 可以转换为"()()" 。
4. "?()?" 可转换为"(())" 。
5. "??" 可转换为"()" 。
6. "()??" 可转换为"()()" 。
7. "??()??" 可转换为"()()() " 。