AT_dwacon5th_final_d Parentheses Inversions

ドワンゴ公司的员工ニワンゴ君非常喜欢括号匹配的字符串。今天，他决定通过重新排列许多括号来进行一场有趣的游戏。 他手里有一个长度为 $N$ 的字符串 $S$，这个字符串仅由 `(` 和 `)` 组成。在字符串 $S$ 中，`(` 和 `)` 的数量是相同的。 我们将满足以下条件的序列 $p$ 称为“好序列”： - $p$ 是对 $1, 2, 3, \ldots, N$ 的一种排列 - 如果我们用 $t_i = s_{p_i}$ 构建字符串 $t$，那么 $t$ 必须是一个“平衡括号序列” 对于所有可能的好序列 $p$，我们要计算它们的逆序数之和，并对结果取模 $10^9 + 7$ 后输出。 其中，序列 $p$ 的逆序数定义为：满足条件 $p_i > p_j$ 的二元组 $(i, j)$ 的数量。平衡括号序列的定义如下： 1. 空字符串被认为是平衡括号序列。 2. 如果 $r$ 是一个平衡括号序列，那么形如 `(`, $r$, `)` 的字符串也是平衡括号序列。 3. 两个平衡括号序列连接起来形成的新字符串依然是平衡括号序列。 4. 只有通过上述规则生成的字符串才被称为平衡括号序列。

输入由一行提供： > $N$ $S$

请输出符合条件的逆序数之和，并取模 $10^9 + 7$。

### 约束条件 - $2 \leq N \leq 5 \times 10^5$ - $S$ 仅包括字符 `(` 和 `)` - 在 $S$ 中，`(` 和 `)` 的数量完全相同 - $|S| = N$ ### 样例说明 例如，对于序列 $p$，可能的排列有 $(1, 2)$ 和 $(2, 1)$。对应的字符串 $t$ 分别是 `)(` 和 `()`。只有排列 $(2, 1)$ 是好序列，其逆序数为 $1$。 请记得在最终答案中对 $10^9 + 7$ 取模。 **本翻译由 AI 自动生成**