小苯的真假游戏

题号：NC304877
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯正在和小朋友们玩游戏，他让所有的小朋友围成一圈， $i$ 号小朋友左侧的是 $i-1$ 号小朋友，特别的： $1$ 号小朋友的左侧是 $n$ 号小朋友。

$\hspace{15pt}$ 现在，已知每个小朋友要么说真话，要么说假话；且每个小朋友都声称自己左侧的小朋友说了：真话（ $\texttt{`1'}$ ）或假话（ $\texttt{`0'}$ ），显然这些 "声称" 里有真有假，因为有些小朋友会说假话。

$\hspace{15pt}$ 你的任务就是求出，在所有可能的不同的局面（即每个小朋友都要么说真话、要么说假话，显然一共有 $2^n$ 个）中，有多少个局面满足：所有小朋友声称的真假性都和他自己说话的真假性一致。
$\hspace{15pt}$ （即：如果其说真话，则其 "声称" 必然是正确的；如果说假话，则其 "声称" 也必然是不正确的。）

输入描述:

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

第一行一个正整数 ，表示小朋友的个数。

第二行一个长度为  的  串 ，表示每一位小朋友都声称自己左侧的人说的话的真假。（如果是  就代表他声称左边的人说的是真话；反正则是假话。）

除此之外，保证单个测试文件的  之和不超过 ，保证  仅由  和  两种字符构成。

输出描述:

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

示例1

输入

复制

输出

复制

2
0

说明

对于第一组测试数据："所有人全说真话" 和 "所有人全说假话" 这两种局面是合法的，因此输出 。