小苯有一个长度为 、仅由字符 和 组成的括号序列 ，且保证这是一个合法括号序列。 现在他想给每个括号染上红色或蓝色，但需要满足以下条件： 每一对相互匹配的括号必须染上相同的颜色（即一个 和它对应的 颜色必须相同） 若序列中两个相邻位置的括号字符相同（同为 或同为 ），则它们的颜色不能相同。 请计算有多少种不同的染色方案。由于答案可能很大，请将答案对 取模后输出。 【名词解释】 合法的括号序列：如果在括号序列中插入字符 和 就可以得到正确的算术表达式，那么这个括号序列就称为合法的括号序列。例如，、 和 是合法的括号序列，因为填入内容后可以表示为 、 和 。更严格地，一个括号序列被称为合法的括号序列，当且仅当： 空串是合法的括号序列； 如果 是合法的括号序列，那么 也是合法的括号序列； 如果 和 都是合法的括号序列，那么 也是合法的括号序列。 相互匹配的括号：在合法括号序列中，若左括号 与右括号 满足 ，且 也是一个合法括号序列，则称这两个位置的括号是相互匹配的。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行一个整数 ，保证 为偶数。第二行一个长度为 、仅由字符 和 组成的括号序列 ，且保证这是一个合法括号序列。除此之外，保证所有测试数据的 之和不超过 。

输出描述:

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