C Tokitsukaze and Balance String (hard)
一道规律题。赛时以为是难的算法题，就没去碰了，实际上把几种情况列出来后可能就会发现，只有首尾相同的字符串才是平衡的。
首先我们容易发现，连续的1或者0是多余的，因为他们对01和10的数量是没有影响的，我们可以将连续的1或者0合并成1个就可以了。
假设s的长度为1，那么显然平衡。
假设s的长度大于等于2：
假设s首尾相同，那么由上面的规律，我们可以将所有情况简单分为11，00，101，10101，010，01010等情况（无非是11，00，101···循环和010···循环）。对于11和00，显然平衡。对于后两种情况也可以推出平衡，因为有10后面必定跟着01，反之亦然。
那么有了这个结论。我们可以发现，如果字符串长度为1可以直接特判。
如果长度大于1，如果首尾相同：
同为'?'，我们可以先将两个'?'改成相同的，然后能修改的就是中间的n-2的位置。再将两个'?'改成不同的，能修改的就只有首尾2个位置，将不同改成相同。答案是将它们相加，再乘上2再乘上中间字符串种类数。
同为'1'或'0'，答案显然就是中间字符串种类数*(n-2)
如果首尾不同：
有一个'?'，与上面第一种情况的第一个类似，只是答案不需要乘2
没有'?'，答案就是中间字符串种类数*2
记得取模
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e6+7;
const int mod = 1e9+7;
int n, m, k, r;
int a[N];
//假如首尾相同,ans就是(n-2)*qmi(2,sum)
//假如首尾不同,ans就是qmi(2,sum)
//两个'?''?'int qmi(int x,int y){int res=1;while(y){if(y&1) res=res*x%mod;y>>=1;x=x*x%mod;}return res;
}void sovle()
{cin>>n;string s;cin>>s;int sum=0;for(int i=1;i<s.size()-1;i++) if(s[i]=='?') sum++;if(s.size()==1){if(s[0]=='?') cout<<2<<endl;else cout<<1<<endl;}else{if(s[0]=='?'&&s[n-1]=='?'){cout<<2*((n-2)*qmi(2,sum)%mod+2*qmi(2,sum)%mod)%mod<<endl;}else if(s[0]=='1'&&s[n-1]=='0'||s[0]=='0'&&s[n-1]=='1') cout<<2*qmi(2,sum)%mod<<endl;else if(s[0]==s[n-1]) cout<<(n-2)*qmi(2,sum)%mod<<endl;else cout<<((n-2)*qmi(2,sum)%mod+qmi(2,sum+1))%mod<<endl;}
}signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int ING = 1;cin>>ING;while (ING--){sovle();}return 0;
}
