配点 : 1500 点
問題文
Dwango 员工 Niwango 喜欢带有匹配括号的字符串。今天,我决定尝试重新排列很多括号。
二王后君是
仅由( 和 ) 组成的长度 N 字符串
我有 S 。S 有
包含相同数量的 ( 和 ) 。
满足以下条件的序列 p 被称为好的序列。 通过重新排列
- (1, 2, 3, ..., N) 获得
- t_i = s_{p_i} 字符串 t 是一组平衡的括号
计算所有好数字的数字序列的跌倒次数,并计算总和。 请打印除以 10^{9}+7 后的余数。
这里的顺序 p 的跌倒次数为 满足p_i > p_j 的配对 定义为 (i, j) (i < j) 的数量。另外,“平衡括号序列”定义如下。
- 空字符串是括号的平衡字符串
- 创建一组平衡的括号 r 。
(, r,)按此顺序连接得到的字符串是一组平衡的括号。 - 2 两个平衡括号序列按此顺序串联是平衡括号序列。
- 上述规则生成的唯一字符串是平衡的括号序列 仅包含
制約
- 2 \leq N \leq 5 \times 10^5
- S 表示
(和)包含相同数量的 - S 表示
(和)包含相同数量的 - |S| = N
入力
输入将以以下格式从标准输入提供。
N S
出力
打印答案。
入力例1
2 )(
出力例1
1
p 的可能序列是 (1, 2), (2, 1) 的 2 每个都有字符串。 t 表示 )( 和 () 。一个好的数列是 (2, 1) 跌倒次数是 1 。
入力例2
6 (())()
出力例2
1060
入力例3
16 )())()((((()))()
出力例3
58589334
- 答案 除以 10^{9}+7 时不要忘记求余数