A. 括号序列

题目描述

给出一个长为 $n$ 的合法括号序列 $s$，求出它是所有长为 $n$ 的合法括号序列按字典序排序后的第几个。答案对 $10^9+7$ 取模。

输入格式

第一行给定 $n$。

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

输出格式

样例 #1

样例输入 #1

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

样例输出 #1

114514

数据范围

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

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