括号（brackets)

题目描述

给出一个长为 $n$ 的合法括号序列 $s$，求出它是所有长为 $n$ 的合法括号序列按字典序排序后的第几个。

答案对 $10^9+7$ 取模。

输入格式

第一行包含一个数 $n$。

第二行包含一个合法括号序列 $s$。

样例数据

样例 1 输入

6
(())()

样例 1 输出

3

样例 2 输入

6
((()))

样例 2 输出

1

样例 3 输入

10
()(()(()))

样例 3 输出

33

样例 4 输入

24
(()(()))((()(()()()())))

样例 4 输出

114514

样例 5

见下发文件。

数据规模与约定

对于所有数据，有 $1 \le n \le 10^7$，$s$ 为合法括号串。

对于 $50\%$ 的数据，有 $1 \le n \le 20$。大样例