問題文

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

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

入力例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 で割った余りを求めるのを忘れずに