当前没有测试数据。

$\hspace{15pt}$本题为《Tokitsukaze and Balance String (easy)》的困难版本，两题的唯一区别在于 $n$ 的范围。

题目描述

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

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

现在 Tokitsukaze 有一个长度为 $n$，仅由字符 $\texttt{`0'}$、$\texttt{`1'}$、$\texttt{`?'}$ 构成的字符串 $s$。
其中，$\texttt{`?'}$ 可以替换成 $\texttt{`0'}$ 或者 $\texttt{`1'}$。假设 $\texttt{`?'}$ 的个数为 $p$，显然将每个 $\texttt{`?'}$ 都替换后，总共可以得到 $2^{p}$ 个不同的 $s$，Tokitsukaze 想知道所有 $2^{p}$ 个不同的 $s$ 对应的 $\rm{val}(s)$ 之和是多少。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 2 \times 10^5\right)$ 代表数据组数，每组测试数据描述如下：
第一行输入一个整数 $n\left(1\leq n\leq 2 \times 10^5\right)$ 代表字符串长度。
第二行输入一个长度为 $n$、仅由 $\texttt{`0'}$、$\texttt{`1'}$、$\texttt{`?'}$ 构成的字符串 $s$。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每一组测试数据，新起一行。输出一个整数，代表全部 $2^p$ 个不同的 $s$ 对应的 $\rm{val}(s)$ 之和。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

样例1

输入

5
1
0
4
??01
5
?????
10
010??1101?
50
??1??0?0???????0?1??00?1???1??0?11??1011001???00??

输出

1
8
80
40
421772709

说明

对于第一组测试数据，反置字符串的第一个字符，得到字符串 $\texttt{"1"}$，此时，$\texttt{"01"}$ 子串与 $\texttt{"10"}$ 子串个数均为 $0$，平衡。由于在这个样例中，只有一种不同的 $s$，所以答案即为 ${\rm val}(\texttt{"1"})=1$。

对于第二组测试数据，通过替换 $\texttt{`?'}$ 得到 $4$ 种不同的 $s$，分别为：$\texttt{"0001"}$、$\texttt{"0101"}$、$\texttt{"1001"}$、$\texttt{"1101"}$。限制于篇幅，我们在此仅详细展开讨论 $\texttt{"0001"}$ 的情况。

• 翻转第一个字符，得到 $\texttt{"1001"}$，此时，$\texttt{"01"}$ 子串与 $\texttt{"10"}$ 子串个数均为 $1$，平衡。
• 翻转第二个字符，得到 $\texttt{"0101"}$，此时，$\texttt{"01"}$ 子串个数为 $2$，$\texttt{"10"}$ 子串个数为 $1$，不平衡。
• 翻转第三个字符，得到 $\texttt{"0011"}$，此时，$\texttt{"01"}$ 子串个数为 $1$，$\texttt{"10"}$ 子串个数为 $0$，不平衡。
• 翻转第四个字符，得到 $\texttt{"0000"}$，此时，$\texttt{"01"}$ 子串与 $\texttt{"10"}$ 子串个数均为 $0$，平衡。
  综上，得到 $\rm{val}(\texttt{"0001"})=2$。
  同理可得其他三个字符串。最终答案为 $2+2+2+2=8$。