1360: 括号计分

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:14 Solved:6

Description

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

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

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

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

Input

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

Output

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

Sample Input Copy

()()()

Sample Output Copy

3

HINT

输入样例2

((()))


输出样例2

4


数据范围

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

- 对于 $50\%$ 的数据,$1\le n\le 200$;
- 对于 $100\%$ 的数据,$1\le n\le 200,000$。

Source/Category