题目描述

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

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

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

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

输入格式

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

输出格式

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

数据范围

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

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

样例数据

输入:

()()()

输出:

3

输入:

((()))

输出:

4