当前没有测试数据。

题目描述

一个字符串是平衡的，当且仅当字符串中 $\texttt{"01"}$ 连续子串的个数与 $\texttt{"10"}$ 连续子串的个数相同。
定义字符串 $s$ 的 $\rm{val}(s)$ 为这样的位置数量：

• 若当前位置上的字符为 $\texttt{`0'}$，将其反置后成为 $\texttt{`1'}$，此时字符串 $s$ 是平衡的；
• 若当前位置上的字符为 $\texttt{`1'}$，将其反置后成为 $\texttt{`0'}$，此时字符串 $s$ 是平衡的。

给定一个长度为 $n$，仅由字符 $\texttt{`0'}$、$\texttt{`1'}$、$\texttt{`?'}$ 构成的字符串 $s$，其中 $\texttt{`?'}$ 可以替换成 $\texttt{`0'}$ 或 $\texttt{`1'}$。假设 $\texttt{`?'}$ 的个数为 $p$，则总共有 $2^{p}$ 个不同的 $s$。需要计算所有 $2^{p}$ 个不同的 $s$ 对应的 $\rm{val}(s)$ 之和，并对 $(10^9+7)$ 取模后输出。

输入描述

• 每个测试文件包含多组测试数据。
• 第一行输入整数 $T$（$1\leq T\leq 10^4$）代表数据组数。
• 每组测试数据包含两行：
  • 第一行输入整数 $n$（$1\leq n\leq 10$）代表字符串长度；
  • 第二行输入长度为 $n$、仅由 $\texttt{`0'}$、$\texttt{`1'}$、$\texttt{`?'}$ 构成的字符串 $s$。

输出描述

• 对于每组测试数据，输出一个整数，代表全部 $2^p$ 个不同的 $s$ 对应的 $\rm{val}(s)$ 之和，对 $(10^9+7)$ 取模后的结果。

样例1

输入

4
1
0
4
??01
5
?????
10
010??1101?

输出

1
8
80
40