Description：

一个 $n\times m$ 的棋盘，每次给出一个 $2\times c$ 的模板，查询包含这个模板的棋盘的方案数。

$1\leqslant n\leqslant 100,1\leqslant m\leqslant 12,1\leqslant c\leqslant 6$

Solution：

轮廓线 $DP$ ，正难则反，统计不包含的方案数， $f[i][j][S][x][y]$ 表示到了第 $i,j$ 个格子，轮廓线和模板的第一行的匹配情况，匹配的位置为 $1$ 不匹配为 $0$ ，轮廓线和第一个模板匹配到 $x$ ，和第二个模板匹配到 $y$ ，一次也不包含模板串的方案数。

然后现在考虑状态的转移，也就是 $(i,j)\to(i,j+1)$ 的转移，如果 $S\&(m-c)\&\&y==c$ 的时候不转移，预先 $KMP$ 求出 $nxta[]$ 和 $nxtb[]$ ，然后再预处理出从某个位置在经过过一个字符 $k$ 后转移到的位置，转移也比较好写，注意细节就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MOD 1000000007

int n,m,c,q;

#define MAXN 110

#define MAXM 12

#define MAXC 7

int f[2][1 << MAXM][MAXC][MAXC];

inline int power(int a,int b)

{

    register int res = 1;

    while(b > 0)

    {

        if(b & 1)res = 1ll * res * a % MOD;

        a = 1ll * a * a % MOD;

        b = b >> 1;

    }

    return res;

}

inline int getc()

{

    register char c = getchar();

    while(c != 'W' && c != 'B' && c != 'X')c = getchar();

    if(c == 'W')return 0;if(c == 'B')return 1;if(c == 'X')return 2;

}

int ta[MAXM],tb[MAXM];

int nxta[MAXM],nxtb[MAXM];

int nxtx[MAXC][3],nxty[MAXC][3];

inline void work()

{

    for(register int i = 1;i <= c;++i)ta[i] = getc();

    for(register int i = 1;i <= c;++i)tb[i] = getc();

    for(register int i = 2,j = 0;i <= c;++i)

    {

        while(j && ta[i] != ta[j + 1])j = nxta[j];

        if(ta[i] == ta[j + 1])++j;

        nxta[i] = j;

    }

    for(register int i = 2,j = 0;i <= c;++i)

    {

        while(j && tb[i] != tb[j + 1])j = nxtb[j];

        if(tb[i] == tb[j + 1])++j;

        nxtb[i] = j;

    }

    for(register int i = 0;i < c;++i)

    {

        for(register int k = 0;k <= 2;++k)

        {

            nxtx[i][k] = i;

            while(nxtx[i][k] && ta[nxtx[i][k] + 1] != k)nxtx[i][k] = nxta[nxtx[i][k]];

            if(ta[nxtx[i][k] + 1] == k)++nxtx[i][k];

        }

    }

    for(register int i = 0;i < c;++i)

    {

        for(register int k = 0;k <= 2;++k)

        {

            nxty[i][k] = i;

            while(nxty[i][k] && tb[nxty[i][k] + 1] != k)nxty[i][k] = nxtb[nxty[i][k]];

            if(tb[nxty[i][k] + 1] == k)++nxty[i][k];

        }

    }

    memset(f,0,sizeof(f));

    f[0][0][0][0] = 1;

    register int cur;

    for(register int i = 1;i <= n;++i)

    {

        cur = 0;

        for(register int j = 0;j < m;++j)

        {

            memset(f[cur ^ 1],0,sizeof(f[cur ^ 1]));

            for(register int s = 0;s < (1 << (m - c + 1));++s)

            {

                register int v = (s >> (j + 1 - c)) & 1;

                for(register int x = 0;x < c;++x)for(register int y = 0;y < c;++y)

                {

                    for(register int k = 0;k <= 2;++k)

                    {

                        register int nx = nxtx[x][k],ny = nxty[y][k],ns = s;;

                        if(ny == c && v == 1)continue;

                        if(j + 1 >= c)

                        {

                            if(nx == c)ns |= (1 << (j + 1 - c));

                            else ns &= ((1 << m) - 1) ^ (1 << (j + 1 - c));

                        }

                        if(nx == c)nx = nxta[nx];

                        if(ny == c)ny = nxtb[ny];

                        f[cur ^ 1][ns][nx][ny] = (f[cur ^ 1][ns][nx][ny] + f[cur][s][x][y]) % MOD;

                    }

                }

            }

            cur ^= 1;

        }

        for(register int s = 0;s < (1 << (m - c + 1));++s)

            for(register int x = 0;x < c;++x)for(register int y = 0;y < c;++y)

                f[0][s][x][y] = f[cur][s][x][y];

    }

    register int ans = 0;

    for(register int s = 0;s < (1 << (m - c + 1));++s)

        for(register int x = 0;x < c;++x)for(register int y = 0;y < c;++y)

            ans = (ans + f[cur][s][x][y]) % MOD;

    cout << (power(3,n * m) - ans + MOD) % MOD << endl;

    return;

}

int main()

{

    scanf("%d%d%d%d",&n,&m,&c,&q);

    for(int i = 1;i <= q;++i)work();

    return 0;

}