看不懂的题
首先考虑 \([a_i\neq b_i]=-2a_ib_i+a_i+b_i\)，所以：
\[f(a,b)=\sum a_i+\sum b_i-2\sum a_ib_i=N-2\sum a_ib_i \]而：
\[\sum_{b'}f(a,b')=N^2-2\sum _{b'}\sum _{i=0}^{N-1}a_ib_i\\ =N^2-2\sum _{i=0}^{N-1}a_i\sum _{b'}b_i=N^2-2\times N^2/4=N^2/2 \]而 \(\sum f(a,b')\ge N^2/2\)，取等当且仅当 \(\forall b',f(a,b')=N/2\)。所以我们知道了 \(f(a,b')=N/2,\forall b'\)。
记 \(N=2^{n+1}\)，用生成函数刻画字符串：
设
\[A=\sum_i a_ix^i,B=\sum _ib_{N-i-1}x^i \]做 \(N\) 长度循环卷积，应该有：
\[[x^n]A*B=[x^n]AB+[x^{n+N}]AB\\ =\sum_{i=0}^n a_ib_{N-n+i-1}+\sum_{i=n+1}^{N-1}a_ib_{i-n-1}\\ =\frac{f(a,b)-\sum a_i-\sum b_i}{-2}=N/4 \]那么：
\[A*B=\frac N4\sum_{i=0}^{N-1}x^{i}=\frac{N(x^N-1)}{4(x-1)}\\ (x-1)*A*B=0 \]可以证明，这是充要的。
考虑这个式子的 DFT 形式：
\[\forall i,DFT_i(x-1)DFT_i(A)DFT_i(B)=0 \]而 \(DFT_i(x-1)\) 仅在 \(i=0\) 时为 \(1\)。
设 \(p_i=DFT_i(A),q_i=DFT_i(B)\)，那么有：
\[\forall 1\le i\le N-1,p_iq_i=0 \]考虑对 \(\lang p_i\rang\) 做蝴蝶变换（长为 \(N\)，就是 FFT 开始那个交换数组），根据 FFT 的过程可以证明：
设 \(t=V_2(n)\)，\(\lang c_i\rang\) 是 \(\lang p_i\rang\) 的蝴蝶变换：
\[p_n=\sum_{i=0}^{2^{n-t}-1}\left(\sum_{l=i2^{t+1}}^{i2^{t+1}+2^t-1}c_l-\sum_{l=i2^{t+1}+2^t}^{i2^{t+1}+2^{t+1}-1}c_l\right)\omega_{2^{n+1-t}}^i \]然后考虑如下性质：
\(\forall N=2^t\ge 1\)，向量空间 \((\Q,\lang\omega_N\rang)\) 的一组基是 \(\omega_N^0,\omega_N^1\dots \omega^{N/2-1}_N\)。
我们注意到这个向量空间的向量乘法满足封闭性。
我们归纳证明这一点。\(t=1\) 时被验证满足。设 \(N=2^t\) 已经证明。
不难发现，\(\omega_{N}^i=-\omega_N^{i-N/2}\)，那么只需证明我们声称的这组基在 \(\Q\) 上线性无关。
假设结果不成立。那么一定有：
\[1=\sum_{i=1}^{N-1}a_i\omega_{2N}^i \]设
\[A=\sum_{i=1,2\mid i}^{N-1}a_{i+1}\omega_{2N}^{i}=\sum_{i=1,2\mid i}^{N-1}a_{i+1}\omega_{N}^{i/2}\\\ B=\sum_{i=1,2\mid i}^{N-1}a_i\omega_{2N}^i=\sum_{i=1,2\mid i}^{N-1}a_i\omega_{N}^{i/2} \]则 \(A,B\in (\Q ,\lang \omega_N\rang)\)。
\[\omega_{2N}A+B=1\\ \omega _NA^2+B^2+2\omega_{2N}AB=1\\ \omega_{2N}=\frac{1-\omega_NA^2-B^2}{2AB}\in(\Q ,\lang \omega_N\rang)\\ \omega_{N}=\left(\frac{1-\omega_NA^2-B^2}{2AB}\right)^2\in(\Q ,\lang \omega_N\rang) \]如果 \(a_i\) 不全为 \(0\)，则此组合是非平凡的，和归纳假设矛盾。证毕。
那么
\[p_n=0\iff \sum_{l=i2^{t+1}}^{i2^{t+1}+2^t-1}c_l-\sum_{l=i2^{t+1}+2^t}^{i2^{t+1}+2^{t+1}-1}c_l=0,\forall i\in [0,2^{n-t}) \]这就是说，对于 \(t=V_2(n)\) 相同的 \(n\)，一定有 \(p_n\) 相同。同时，这个条件等价于所有 \([i2^{t+1},i2^{t+1}+2^t)\) 和 \([i2^{t+1}+2^t,i2^{t+1}+2^{t+1})\) 的 \(1\) 个数相同。
那我们求出 \(c\) 之后尝试 dp 解决问题。枚举 \(S\) 为 \(1\) 的位置集合，尝试求出 \(f_S\)，即这些位置是 \(1\) 的方案数。把这个当成 FFT 的满二叉树结构。设 \(dp(i,j,x)\) 为第 \(i\) 层，\(j\) 棵子树，里面有 \(x\) 个 \(1\) 的方案数，向上合并即可。
过不了。注意到和 FFT 改变 \(\omega\) 的角标类似，\(x\) 在 \(S\) 钦定下面有 \(c\) 个 \(1\) 之后只需要把 \(2^c\) 作为单位：必须整除 \(2^c\)。这时需要把集合扔进去。设 \(dp(i,S,j,x)\) 是第 \(i\) 层，\(j\) 棵子树，\(S\) 是下面所选的集合。设 \(c=|S|\)，\(x\) 意思是里面有 \(x\times 2^c\) 个 \(1\) 的方案数，向上合并即可。这个过程是卷积：如果钦定 \(S\) 选，那么必须左右子树大小相等。否则就是普通卷积。
时间复杂度是 \(O(5^n)\)。但是常数不小所以没过（回来吧 C++20），使用 NTT 优化后是 \(O(n3^n)\)，可以通过。
// Problem: Cyclic Hamming (Hard Version)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1896H2
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// UOB Koala'
//
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ull unsigned long long
#pragma GCC optimize("Ofast")
const int maxn=83000,mod=998244353,G=3,iG=(mod+1)/3;
int k,n;
char s[maxn],t[maxn];
int f[maxn],g[maxn],U;
#define VI vector<int>
int r[maxn],lim,L,R[maxn];
void predo(int n){
lim=1,L=0;
while(lim<=n)lim<<=1,L++;
for(int i=1;i<lim;i++)R[i]=(R[i>>1]>>1)|((i&1)<<L-1);
}
int qp(int a,int b){
if(b==0)return 1;
int T=qp(a,b>>1);T=1ll*T*T%mod;
if(b&1)return 1ll*T*a%mod;
return T;
}
int TTT[maxn];
ull a[maxn];
inline void ntt(VI &A,int tp){
TTT[0]=1;
for(int i=0;i<lim;i++)a[i]=A[i];
for(int i=0;i<lim;i++)if(R[i]>i)swap(a[i],a[R[i]]);
for(int mid=1;mid<lim;mid<<=1){
int wn=qp(tp==1?G:iG,(mod-1)/(mid<<1));
for(int j=1;j<mid;j++)TTT[j]=1ll*TTT[j-1]*wn%mod;
for(int j=0;j<lim;j+=(mid<<1)){
for(int k=0;k<mid;k++){
ull x=a[j+k],y=a[j+k+mid]*TTT[k]%mod;
a[j+k]=(x+y),a[j+k+mid]=(x-y+mod);
}
}
if(mid==(1<<15))for(int j=0;j<lim;j++)a[j]%=mod;
}
for(int j=0;j<lim;j++)a[j]%=mod;
if(tp==-1){
int I=qp(lim,mod-2);
for(int i=0;i<lim;i++)a[i]=1ll*a[i]*I%mod;
}
for(int i=0;i<lim;i++)A[i]=a[i];
}
VI operator *(VI a,VI b){
VI Ans;
if(a.size()+b.size()<300){
Ans.resize(a.size()+b.size()-1);
for(int i=0;i<a.size();i++){
for(int j=0;j<b.size();j++){
Ans[i+j]=(Ans[i+j]+1ll*a[i]*b[j])%mod;
}
}
}else{
int len=a.size()+b.size()-1;
predo(len);
a.resize(lim),b.resize(lim),Ans.resize(lim);
ntt(a,1);ntt(b,1);
for(int i=0;i<lim;i++)Ans[i]=1ll*a[i]*b[i]%mod;
ntt(Ans,-1);
Ans.resize(len);
}
return Ans;
}
void calc(int f[],char s[]){
for(int i=1;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)<<k-1);
for(int i=1;i<n;i++)if(i>r[i])swap(s[i],s[r[i]]);
static vector<vector<VI > > dp[15];
for(int t=0;t<=k;t++){
dp[t].resize(1<<t);
for(int S=0;S<(1<<t);S++){
dp[t][S].resize(1<<k-t);
for(int x=0;x<(1<<k-t);x++){
dp[t][S][x].resize(1+(1<<t-__builtin_popcount(S)));
for(int i=0;i<=(1<<t-__builtin_popcount(S));i++)dp[t][S][x][i]=0;
}
}
}
for(int i=0;i<(1<<k);i++){
if(s[i]!='1')dp[0][0][i][0]=1;
if(s[i]!='0')dp[0][0][i][1]=1;
}
for(int t=1;t<=k;t++){
for(int S=0;S<(1<<t-1);S++){
for(int x=0;x<(1<<k-t);x++){
int c=(1<<t-__builtin_popcount(S)-1);
dp[t][S][x]=dp[t-1][S][x*2]*dp[t-1][S][x*2+1];
for(int i=0;i<=c;i++){
dp[t][S|(1<<t-1)][x][i]=1ll*dp[t-1][S][x*2][i]*dp[t-1][S][x*2+1][i]%mod;
}
}
}
}
// exit(0);
for(int i=0;i<(1<<k)-1;i++)f[i]=dp[k][i][0][1<<(k-1-__builtin_popcount(i))];
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>k>>s>>t;
k++,n=(1<<k);U=(1<<k)-1;
reverse(t,t+n);
calc(f,s);calc(g,t);
for(int j=0;j<k;j++)
for(int i=0;i<(1<<k);i++)
if(!(i&(1<<j)))
(f[i]-=f[i^(1<<j)]-mod)%=mod;
int ans=0;
for(int i=0;i<(1<<k);i++)(ans+=1ll*g[i]*f[U-i]%mod)%=mod;
cout<<ans<<endl;
return 0;
}