LG3290

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int p=1e9+7;
const int N=205;
const int M=15;

inline void add(int &a,int b){
    if((a+=b)>=p)a-=p;
}

inline int index(char c){
    switch(c){
        case 'W':return 0;
        case 'B':return 1;
        default :return 2;
    }
}

int n,m,c,T,len;

inline void GetNext(int *Next,int *S){
    for(int i=2,j=0;i<=c;++i){
        while(j&&S[i]!=S[j+1])j=Next[j];
        if(S[i]==S[j+1])j++;
        Next[i]=j;
    }
}

inline int kmp(int *S,int *Next,int x,int ch){
    while(x&&S[x+1]!=ch)x=Next[x];
    if(S[x+1]==ch)x++;
    return x;
}

char s1[M];
char s2[M];
int A[M];
int B[M];
int nx1[M];
int nx2[M];
int f[2][(1<<12)|7][7][7];

int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    r(n),r(m),r(c),r(T);
    len=m-c+1;
    while(T--){
        memset(f,0,sizeof(f));
        scanf("%s%s",s1+1,s2+1);
        for(int i=1;i<=c;++i)A[i]=index(s1[i]);A[0]=A[c+1]=-1;
        for(int i=1;i<=c;++i)B[i]=index(s2[i]);B[0]=B[c+1]=-1;
        GetNext(nx1,A);
        GetNext(nx2,B);
        bool cur;
        f[cur][0][0][0]=1;
        ll power=1;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                (power*=3)%=p;
                for(int s=0;s<(1<<len);++s){
                    for(int a=0;a<=c;++a){
                        for(int b=0;b<=c;++b){
                            if(!f[cur][s][a][b])continue;
                            for(int ch=0;ch<3;++ch){
                                int x=kmp(A,nx1,a,ch);
                                int y=kmp(B,nx2,b,ch);
                                int t=s;
                                if(j>=c){
                                    t&=(~(1<<(j-c)));
                                    t|=(x==c)<<(j-c);
                                }
                                if(j>=c&&(s>>(j-c)&1)&&y==c)continue;
                                add(f[cur^1][t][x][y],f[cur][s][a][b]);
                            }
                            f[cur][s][a][b]=0;
                        }
                    }
                }
                cur^=1;
            }
            for(int s=0;s<(1<<len);++s){
                int sum=0;
                for(int a=0;a<=c;++a){
                    for(int b=0;b<=c;++b){
                        add(sum,f[cur][s][a][b]);
                        f[cur][s][a][b]=0;
                    }
                }
                f[cur][s][0][0]=sum;
            }
        }
        int ans=0;
        for(int s=0;s<(1<<len);++s){
            add(ans,f[cur][s][0][0]);
        }
        printf("%lld\n",(power-ans+p)%p);
    }
}