题目描述

小C拿到了 $n$ 个较短的括号串。小C想知道，用这 $n$ 个短括号串前后拼接成一个合法的括号串，有多少种不同的拼接方案。

（注意：每个括号都要用恰好一次。）

输入格式

输入文件名:mate.in

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ $(1 \leq T \leq 10)$ 代表数据组数，每组测试数据描述如下：

• 第一行一个正整数 $n$ $(1 \leq n \leq 20)$，表示短括号串的个数
• 接下来 $n$ 行，每行一个括号串 $s$ $(1 \leq |s| \leq 10^6)$，表示每个短括号串（保证只由 $'('$ 和 $')'$ 两种字符构成）

除此之外，保证单个测试文件的 $|s|$ 之和不超过 $10^6$。

输出格式

输出文件名:mate.out

对于每组测试数据：

在单独的一行输出一个整数，表示合法的拼接方案个数（由于答案可能很大，因此输出答案对 $10^9 + 7$ 取模的值）。

（注意：是合法的拼接方案数，并非合法的本质不同结果括号串数，详见样例。）

样例

2
4
((
))
(
)
3
()
()()
()()

7
6

提示

对于第二组测试数据，所有的拼接方案：$\{1,2,3\}$、$\{1,3,2\}$、$\{2,1,3\}$、$\{2,3,1\}$、$\{3,1,2\}$、$\{3,2,1\}$ 均是合法的，因此输出 $6$。

数据范围

前 $10\%$ 的数据，保证给定的括号本身就是合法的。

前 $40\%$ 的数据，$1 \le n \le 5$

前 $100\%$ 的数据，$1 \le t \le10,1 \le n \le 20$,保证单个测试文件的 $|s|$ 之和不超过 $10^6$，同时给定的字符串只包含(和)。