难得出一个AC自动机，我还没做到这个题呢。。。这题思路不难想，小小的状压出一维来，不过，D和R，让我wa死了，AC自动机，还得刷啊。。。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define MOD 1000000007
int dp[][][][];
int trie[][];
int o[];
int fail[],que[],p[][];
int t;
void CL()
{
t = ;
memset(trie,-,sizeof(trie));
memset(o,,sizeof(o));
memset(p,,sizeof(p));
}
void insert(char *s,int x)
{
int i,root,len,temp;
len = strlen(s);
root = ;
for(i = ; i < len; i ++)
{
temp = s[i] == 'D' ? :;
if(trie[root][temp] == -)
trie[root][temp] = t ++;
root = trie[root][temp];
}
o[root] = <<x;
}
void build_ac()
{
int head,tail,front,i;
head = tail = ;
for(i = ; i < ; i ++)
{
if(trie[][i] != -)
{
fail[trie[][i]] = ;
que[tail++] = trie[][i];
}
else
trie[][i] = ;
}
while(head != tail)
{
front = que[head++];
o[front] |= o[fail[front]];
for(i = ; i < ; i ++)
{
if(trie[front][i] != -)
{
que[tail++] = trie[front][i];
fail[trie[front][i]] = trie[fail[front]][i];
}
else
{
trie[front][i] = trie[fail[front]][i];
}
}
}
}
int main()
{
int cas,i,j,k,u,n,m,temp;
char str[];
scanf("%d",&cas);
while(cas--)
{
CL();
scanf("%d%d",&n,&m);
for(i = ; i < ; i ++)
{
scanf("%s",str);
insert(str,i);
}
for(i = ; i <= n; i ++)
{
for(j = ; j <= m; j ++)
{
for(k = ; k < t; k ++)
{
for(u = ; u < ; u ++)
dp[i][j][k][u] = ;
}
}
}
build_ac();
dp[][][][] = ;
for(i = ; i <= n; i ++)
{
for(j = ; j <= m; j ++)
{
for(k = ; k < t; k ++)
{
for(u = ; u < ; u ++)
{
if(i != n)
{
temp = trie[k][];
dp[i+][j][temp][u|o[temp]] = (dp[i+][j][temp][u|o[temp]] + dp[i][j][k][u])%MOD;
}
if(j != m)
{
temp = trie[k][];
dp[i][j+][temp][u|o[temp]] = (dp[i][j+][temp][u|o[temp]] + dp[i][j][k][u])%MOD;
}
}
}
}
}
int ans = ;
for(i = ; i < t; i ++)
{
ans = (ans + dp[n][m][i][])%MOD;
}
printf("%d\n",ans);
}
return ;
}