下面是核心代码：
```cpp
chr C[2][25];
uint Ok[2][531443],Op[25],Nxt[25][3];
uint A[531443],B[531443],Id[1025],Stt[1025],tp,tp2;
modint W[1025],Last[1025],Cnt[531443];
typedef std::pair<uint,uint>Pair;
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
#endif
uint n,m,c,q;scanf("%u%u%u%u",&n,&m,&c,&q);uint SLim=power(3u,m,-1u);
while(q--){
scanf("%s%s",C[0],C[1]);
for(uint op=0;op<2;op++){
for(uint i=0;i<c;i++)Op[i]=C[op][i]=='W'?2:(C[op][i]=='B');
for(uint k=0;k<3;k++)Nxt[0][k]=0;
Nxt[0][Op[0]]=1;
uint j=0;
for(uint i=1;i<c;i++){
for(uint k=0;k<3;k++)Nxt[i][k]=Nxt[j][k];
Nxt[i][Op[i]]=i+1,j=Nxt[j][Op[i]];
}
for(uint k=0;k<3;k++)Nxt[c][k]=Nxt[j][k];
for(uint S=0;S<SLim;S++)
{
uint at=0,v=0,T=S;
for(uint i=0;i<m;i++)at=Nxt[at][T%3],T/=3,v|=(at==c)<<i;
Ok[op][S]=v>>(c-1);
}
}
std::map<Pair,uint>M;std::set<uint>T;
for(uint i=0;i<SLim;i++)
M[{Ok[0][i],Ok[1][i]}]++,T.insert(Ok[0][i]);
T.insert(0);
tp=tp2=0;
for(auto v:M)A[tp]=v.first.first,B[tp]=v.first.second,Cnt[tp]=v.second,tp++;
for(auto v:T)Stt[Id[v]=tp2]=v,W[tp2]=0,tp2++;
W[0]=1;
modint ans;
for(uint cnt=0;cnt<n;cnt++){
for(uint i=0;i<tp2;i++)Last[i]=W[i],W[i]=0;
for(uint i=0;i<tp2;i++)for(uint j=0;j<tp;j++){
if(Stt[i]&B[j])ans+=Last[i]*Cnt[j]*(modint(3)^(m*(n-cnt-1)));
else W[Id[A[j]]]+=Last[i]*Cnt[j];
}
}
ans.println();
}
return 0;
}
```
by myee @ 2022-10-18 14:50:19
@[myee](/user/105050) 数据范围不是明确写出来了？
by SilviaLss @ 2022-10-18 16:17:30
@[Silviasylvia](/user/121275) 看看数据点 $9$。
by myee @ 2022-10-18 17:27:54
$$6^8\times100=167961600>10^8$$
by myee @ 2022-10-18 17:29:31
@[myee](/user/105050) 这年代你还拿 $10^8$ 为界？
by 猫猬兽 @ 2022-10-19 20:34:34