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$ 的余数。
对平衡的括号序列,定义一种计分规则如下:
- 如果只有一对括号 (),只算 $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$。
((()))
输出样例2
4
数据范围
设 $n$ 表示输入字符串的长度,
- 对于 $50\%$ 的数据,$1\le n\le 200$;
- 对于 $100\%$ 的数据,$1\le n\le 200,000$。