传送门
题解可以参见zjjzjjzjj神仙的，写的很清楚。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
const int mod=1e9+7;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline void update(int&a,const int&b){a=add(a,b);}
inline void modify(int&a,const int&b){a=dec(a,b);}
int ans,f[2][1<<12|5][13][13],n,m,c,q,a[13],fail[2][13],trans[2][13][3],tmp;
char s[13];
inline int idx(const char&x){return x=='W'?0:(x=='B'?1:2);}
int main(){
scanf("%d%d%d%d",&n,&m,&c,&q);
while(q--){
for(ri tt=0;tt<2;++tt){
scanf("%s",s+1);
for(ri i=1;i<=c;++i)a[i]=idx(s[i]);
for(ri i=1,j=0;i<=c;++i){
while(j&&s[i+1]!=s[j+1])j=fail[tt][j];
s[i+1]==s[j+1]?fail[tt][i+1]=++j:fail[tt][i+1]=0;
}
for(ri k,i=0;i<c;++i)for(ri j=0;j<3;++j){
for(k=i;k&&a[k+1]!=j;k=fail[tt][k]);
trans[tt][i][j]=a[k+1]==j?k+1:0;
}
}
memset(f[0],0,sizeof(f[0]));
ans=f[0][0][0][0]=1,tmp=1;
for(ri i=1;i<=n;++i){
memset(f[tmp],0,sizeof(f[tmp]));
for(ri j=0,up=1<<(m-c+1);j<up;++j)for(ri k=0;k<c;++k)for(ri l=0;l<c;++l)update(f[tmp][j][0][0],f[tmp^1][j][k][l]);
tmp^=1;
for(ri j=1;j<=m;++j,tmp^=1){
ans=mul(ans,3);
memset(f[tmp],0,sizeof(f[tmp]));
for(ri sta=0,up=1<<(m-c+1);sta<up;++sta)for(ri k=0;k<c;++k)for(ri l=0;l<c;++l){
if(!f[tmp^1][sta][k][l])continue;
for(ri a,b,ns,t=0;t<3;++t){
a=trans[0][k][t],b=trans[1][l][t],ns=sta;
if(j>=c&&((sta>>(j-c))&1))ns^=1<<(j-c);
if(a==c)ns^=1<<(j-c),a=fail[0][a];
if(b==c){if((sta>>(j-c))&1)continue;b=fail[1][b];}
update(f[tmp][ns][a][b],f[tmp^1][sta][k][l]);
}
}
}
}
tmp^=1;
for(ri i=0,up=1<<(m-c+1);i<up;++i)for(ri j=0;j<c;++j)for(ri k=0;k<c;++k)modify(ans,f[tmp][i][j][k]);
cout<<ans<<'\n';
}
return 0;
}