AT_dwacon5th_final_d Parentheses Inversions

[problemUrl]: https://atcoder.jp/contests/dwacon5th-final/tasks/dwacon5th_final_d ドワンゴ社員のニワンゴ君は、括弧の対応が取れた文字列が大好きです。今日は、たくさんの括弧を並び替えて遊ぶことにしました。 ニワンゴくんは、`(` と `)` のみからなる長さ $ 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\ の個数として定義されます。また、「バランスの取れた括弧列」は以下のように定義されます。 $ 1. 空文字列はバランスの取れた括弧列である 2. バランスの取れた括弧列を $ r $ とする。 `(`, $ r $, `)` をこの順に連結して得られる文字列はバランスの取れた括弧列である 3. $ 2 $ つのバランスの取れた括弧列をこの順に連結したものはバランスの取れた括弧列である 4. 上記の規則によって生成される文字列のみがバランスの取れた括弧列である

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 5\ \times\ 10^5 $ - $ S $ は `(` と `)` のみからなる - $ S $ は `(` と `)` を同じ数含む - $ |S|\ =\ N $ ### Sample Explanation 1 $ p $ としてありえる数列は $ (1,\ 2),\ (2,\ 1) $ の $ 2 $ 通りあり、それぞれに対する文字列 $ t $ は `)(` と `()` です。いい数列は $ (2,\ 1) $ だけであり、この転倒数は $ 1 $ です。 ### Sample Explanation 3 \- 答えを $ 10^{9}+7 $ で割った余りを求めるのを忘れずに