問題文

ドワンゴ社員のニワンゴ君は、括弧の対応が取れた文字列が大好きです。今日は、たくさんの括弧を並び替えて遊ぶことにしました。

ニワンゴくんは、( と ) のみからなる長さ $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$

入力例1Copy

2
)(

出力例1Copy

1

$p$ としてありえる数列は $(1, 2), (2, 1)$ の $2$ 通りあり、それぞれに対する文字列 $t$ は )( と () です。いい数列は $(2, 1)$ だけであり、この転倒数は $1$ です。

入力例2Copy

6
(())()

出力例2Copy

1060

入力例3Copy

16
)())()((((()))()

出力例3Copy

58589334

• 答えを $10^{9}+7$ で割った余りを求めるのを忘れずに