← 返回题目列表

Codeforces · 785/D

D. 安东和学校 - 2

中文机器翻译题面 查看原题

您可能知道,安东去上学。安东学习的学校科目之一是括号学。在括号学课程中,学生通常学习由圆括号(字符“(”和“)”(不带引号)组成的不同序列。

在上一课中,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。