问题描述

DWANGO员工Niwango喜欢括号匹配的字符串。今天，他决定玩一下重新排列括号的游戏。

Niwango有一个仅由(和)组成的长度为N的字符串S，其中S中包含相同数量的(和)。

称满足以下条件的数列p为好数列：

• 对于 $(1, 2, 3, ..., N)$ 进行重新排列得到
• 字符串 $t$ 满足 $t_i = s_{p_i}$，即$t$是一个平衡的括号序列

计算所有好数列的逆序对数，并输出其和对 $10^{9}+7$ 取余。

这里，数列p的逆序对数被定义为满足$p_i > p_j$的数对$(i, j)$（$i < j$）的个数。而“平衡的括号序列”定义如下：

1. 空字符串是平衡的括号序列
2. 若$r$是平衡的括号序列，则字符串(、$r$和)按顺序拼接得到的字符串也是平衡的括号序列
3. 若两个平衡的括号序列按顺序拼接得到的字符串也是平衡的括号序列
4. 只有通过上述规则生成的字符串才是平衡的括号序列

约束条件

• $2 \leq N \leq 5 \times 10^5$
• $S$ 只包含(和)
• $S$ 中包含相同数量的(和`)$
• $|S| = N$

输入

输入按以下格式从标准输入中给出。

$N$ $S$

输出

输出答案。

输入示例1

2
)(

输出示例1

1

$p$ 的可能数列有 $(1, 2)$ 和 $(2, 1)$，对应的字符串 $t$ 分别是)(和()。满足条件的好数列只有$(2, 1)$，它的逆序对数为1。

输入示例2

6
(())()

输出示例2

1060

输入示例3

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

输出示例3

58589334

不要忘记将答案对 $10^{9}+7$ 取余。