← 返回题目列表

AtCoder · dwacon5th_final_d

D. 括号倒置

中文机器翻译题面 查看原题

配点 : 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) 的数量。另外,“平衡括号序列”定义如下。

  1. 空字符串是括号的平衡字符串
  2. 创建一组平衡的括号 r 。 (, r, ) 按此顺序连接得到的字符串是一组平衡的括号。
  3. 2 两个平衡括号序列按此顺序串联是平衡括号序列。
  4. 上述规则生成的唯一字符串是平衡的括号序列 仅包含

制約

  • 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 时不要忘记求余数