小苯正在和小朋友们玩游戏，他让所有的小朋友围成一圈， 号小朋友左侧的是 号小朋友，特别的： 号小朋友的左侧是 号小朋友。 现在，已知每个小朋友要么说真话，要么说假话；且每个小朋友都声称自己左侧的小朋友说了：真话（）或假话（），显然这些 "声称" 里有真有假，因为有些小朋友会说假话。 你的任务就是求出，在所有可能的不同的局面（即每个小朋友都要么说真话、要么说假话，显然一共有 个）中，有多少个局面满足：所有小朋友声称的真假性都和他自己说话的真假性一致。 （即：如果其说真话，则其 "声称" 必然是正确的；如果说假话，则其 "声称" 也必然是不正确的。）

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行一个正整数 ，表示小朋友的个数。第二行一个长度为 的 串 ，表示每一位小朋友都声称自己左侧的人说的话的真假。（如果是 就代表他声称左边的人说的是真话；反正则是假话。）除此之外，保证单个测试文件的 之和不超过 ，保证 仅由 和 两种字符构成。

输出描述:

对于每组测试数据：在单独的一行输出一个整数，表示在所有可能的不同局面中，合法局面的个数。（即每个人说话的真假都和自己声称的真假性一致。）（由于结果可能很大，因此输出结果对 取模的值。）