您可能知道,安东去上学。安东学习的学校科目之一是括号学。在括号学课程中,学生通常学习由圆括号(字符“(”和“)”(不带引号)组成的不同序列。
在上一课中,Anton 学习了常规简单括号序列 (RSBS)。如果满足以下条件,长度为 n 的括号序列 s 就是 RSBS:
- 它不为空(即 n ≠ 0)。
- 序列的长度是偶数。
- 序列的第一个 $$\frac{\pi}{2}$$ 字符等于“(”。
- 序列的最后 $$\frac{\pi}{2}$$ 字符等于“)”。
例如,序列“((()))”是RSBS,但序列“((())”和“(()())”不是RSBS。
安东的老师埃琳娜·伊万诺夫娜 (Elena Ivanovna) 给了他以下任务作为家庭作业。给定一个括号序列 s。求其不同子序列的数量,使得它们是 RSBS。请注意,s 的子序列是一个字符串,可以通过删除 s 的一些元素来从 s 中获得。如果删除不同的位置集,则两个子序列被认为是不同的。
因为答案可能非常大,而且安东的老师不喜欢大数字,所以她要求安东以 109 + 7 为模求出答案。
安东想了这个任务很长时间,但他仍然不知道如何解决。帮助安东解决这个任务并编写一个程序来找到它的答案!
输入
输入的唯一一行包含字符串 s — Anton 作业中给出的括号序列。该字符串仅由字符“(”和“)”组成(不带引号)。保证字符串不为空且长度不超过200000。
输出
输出一个数字——任务的答案以 109 + 7 为模。
示例
输入 #1
)(()()
输出 #1
6
输入 #2
()()()
输出 #2
7
输入 #3
)))
输出 #3
0
注意
在第一个示例中,可能存在以下子序列:
- 如果我们删除位置 1 和 5 处的字符(编号从 1 开始),我们将得到子序列“(())”。
- 如果我们删除位置 1、2、3 和 4 处的字符,我们将得到子序列“()”。
- 如果我们删除位置 1、2、4 和 5 处的字符,我们将得到子序列“()”。
- 如果我们删除位置 1、2、5 和 6 处的字符,我们将得到子序列“()”。
- 如果我们删除位置 1、3、4 和 5 处的字符,我们将得到子序列“()”。
- 如果我们删除位置 1、3、5 和 6 处的字符,我们将得到子序列“()”。
其余子序列不是 RSBS。所以我们得到了 6 个不同的 RSBS 子序列,所以答案是 6。