小苯有一个长度为 、仅由字符 和 组成的括号序列 ，且保证这是一个合法括号序列。

现在他想给每个括号染上红色或蓝色，但需要满足以下条件：
每一对相互匹配的括号必须染上相同的颜色（即一个 和它对应的 颜色必须相同）
若序列中两个相邻位置的括号字符相同（同为 或同为 ），则它们的颜色不能相同。

请计算有多少种不同的染色方案。由于答案可能很大，请将答案对 取模后输出。

【名词解释】
合法的括号序列：如果在括号序列中插入字符 和 就可以得到正确的算术表达式，那么这个括号序列就称为合法的括号序列。例如，、 和 是合法的括号序列，因为填入内容后可以表示为 、 和 。更严格地，一个括号序列被称为合法的括号序列，当且仅当：
空串是合法的括号序列；
如果 是合法的括号序列，那么 也是合法的括号序列；
如果 和 都是合法的括号序列，那么 也是合法的括号序列。

相互匹配的括号：在合法括号序列中，若左括号 与右括号 满足 ，且 也是一个合法括号序列，则称这两个位置的括号是相互匹配的。

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

第一行一个整数 ，保证  为偶数。
第二行一个长度为 、仅由字符  和  组成的括号序列 ，且保证这是一个合法括号序列。

除此之外，保证所有测试数据的  之和不超过 。

对于每组数据，新起一行输出一个整数，表示染色方案数对  取模后的结果。

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

2
2
4