该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

括号序列是由 ( 与 ) 构成的序列。平衡的括号序列要求 ( 与 ) 出现次数一样多，而且序列的每个前缀里 ( 出现次数不低于 ) 的出现次数。

对平衡的括号序列，定义一种计分规则如下：

1. 如果只有一对括号 ()，只算 $1$ 分；
2. (A) 的分数是 $A$ 的 $2$ 倍；
3. $AB$ 的分数是 $A$ 与 $B$ 的和，其中 $A$ 与 $B$ 必须是平衡的括号序列。

给定一个平衡的括号序列，请计算它的分数，由于数字可能很大，输出答案模 $1,000,000,007$ 的余数。

输入格式

单个字符串：表示输入的序列。

输出格式

单个整数：表示括号序列的分数模 $1,000,000,007$ 的余数。

()()()

3

((()))

4

数据规模与约定

设 $n$ 表示输入字符串的长度，

• 对于 $50\%$ 的数据，$1 \leq n \leq 200$；
• 对于 $100\%$ 的数据，$1 \leq n \leq 200,000$。