F-Bracket Counting_牛客周赛 Round 112

时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有一个括号串 $S$ ，但这天淘气的小红将 $S$ 切分成了恰好 $n$ 个更短的括号串。小苯想知道，用这 $n$ 个短括号串前后拼接复原出一个合法的括号串，有多少种不同的拼接方案。
$\hspace{15pt}$ （注意：每个括号都要用恰好一次。）

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行一个正整数 ，表示短括号串的个数。
接下来  行，每行一个括号串 ，表示每个短括号串。（保证只由 '(' 和 ')' 两种字符构成。）

除此之外，保证单个测试文件的  之和不超过 。

对于每组测试数据：
在单独的一行输出一个整数，表示合法的拼接方案个数。（由于答案可能很大，因此输出答案对  取模的值。）
（注意，是合法的拼接方案数，并非合法的本质不同结果括号串数，详见样例。）

示例1

复制

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

复制

12
6

对于第二组测试数据，所有的拼接方案： 均是合法的，因此输出 。