题目描述

给出一个长度为 $2\times n$ 的、非空的、合法的括号序列$^\texttt{[1]}$$s$，其有 $n$ 个匹配的括号对。 你需要给每一对匹配的括号对赋值，满足： $\hspace{23pt}\bullet\,$所有括号对的权值形成一个长为 $n$ 的排列$^\texttt{[2]}$； $\hspace{23pt}\bullet\,$如果括号对 $A$ 在括号对 $B$ 的内层，$A$ 的权值必须大于 $B$ 的权值。 请你计算满足条件的赋值方案一共有多少种。由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模后的值。 【名词解释】 合法的括号序列$^\texttt{[1]}$：如果在括号序列中插入字符 $\texttt{+}$ 和 $\tt 1$ 就可以得到正确的算术表达式，那么这个括号序列就称为合法的括号序列。例如，$\texttt{$、$\texttt{$ 和 $\texttt{$ 是合法的括号序列，因为填入内容后可以表示为 $\texttt{$、$\texttt{$ 和 $\texttt{$。更严格地，一个括号序列被称为合法的括号序列，当且仅当： ${\hspace{23pt}}\texttt{1.}\,$空串是合法的括号序列； ${\hspace{23pt}}\texttt{2.}\,$如果 $A$ 是合法的括号序列，那么 $\texttt{$ 也是合法的括号序列； ${\hspace{23pt}}\texttt{3.}\,$如果 $A$ 和 $B$ 都是合法的括号序列，那么 $AB$ 也是合法的括号序列。 本题需要特别指出内外层的定义：对于上述的第 $2$ 种添加方式，新添加的括号对在 $A$ 中所有括号对的外层。 长度为 $n$ 的排列$^\texttt{[2]}$：由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如，$\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。官方中文

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $t\ (1\le t\le10^4)$ 代表数据组数，每组测试数据描述如下：官方中文

第一行输入一个整数 $n\ (1\le n\le 5\times10^5)$，表示 $s$ 的括号对数量。 第二行输入一个合法括号序列 $s$ ，表示其内容。官方中文

除此之外保证单个测试文件的 $n$ 之和不超过 $5\times10^5$ 。官方中文

输出格式

对于每组测试数据，新起一行输出一个整数，表示答案对 $10^9+7$ 取模后的值。官方中文