题目内容

考古学家发掘出一段古老的符文序列，每个符文固定为两种基本属性之一：阳（记为 1）或阴（记为 0）。由于风化侵蚀，部分符文已经无法辨认，位置被替换为占位符 ?。你需要将每一个 ? 独立地替换为 0 或 1，从而恢复出一段完整的序列。

我们定义序列的一个 极长同属性段 为一段连续且不能向两端扩展的相同属性符文组成的子串。恢复后的序列必须满足：每一个极长同属性段的长度都是奇数。请计算所有可能的合法填充方案总数。

由于答案可能很大，结果需要对 $10^9+7$ 取模。

约束条件

• 每个符文序列的长度 $n$ 满足 $1 \le n \le 2 \times 10^5$。
• 测试数据组数 $T$ 满足 $1 \le T \le 10^5$。
• 所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输入描述

第一行包含一个整数 $T$，表示测试数据的组数。接下来依次给出每组数据：第一行包含一个整数 $n$，表示符文序列的长度；第二行包含一个长度为 $n$ 且仅由字符 0、1、? 组成的字符串，表示原始的受损序列。

输出描述

对于每组测试数据，输出一行一个整数，表示满足条件的填充方案数，结果对 $10^9+7$ 取模。

样例1

输入

1
1
?

输出

2

说明

序列仅包含 1 个字符 ?，可以独立替换为 0 或 1。无论哪种选择，最终的序列都只包含一个极长同属性段，长度为 1，是奇数。因此共有 2 种合法方案。

样例2

输入

1
3
1?1

输出

2

说明

已知序列为 1?1，中间的 ? 有两种填法：

• 填 0：得到 101，极长段依次为 1、0、1，长度均为 1（奇数），合法。
• 填 1：得到 111，只有一个极长段 111，长度为 3（奇数），合法。

两种填充均满足要求，方案总数为 2。

样例3

输入

1
3
0?1

输出

0

说明

序列为 0?1，考虑 ? 的两种可能：

• 若填 0，得到 001，极长段 00 的长度为 2（偶数），不满足奇数要求。
• 若填 1，得到 011，极长段 11 的长度为 2（偶数），同样不合法。

无论哪种选择都会产生偶数长度的极长段，因此不存在合法方案，答案为 0。

样例4

输入

1
5
0??0?

输出

2

说明

序列包含 3 个 ?，可以通过动态规划计算合法方案。所有合法填充共有 2 种，例如：

• 全部填 0，得到 00000，唯一极长段长度为 5（奇数），合法。
• 填为 01000，极长段依次为 0（长度 1）、1（长度 1）、000（长度 3），均为奇数。

其余填充方式（如 00100、01100 等）均会产生偶数长度的极长段，故总方案数为 2。