#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

typedef int DATA;
const int MAXL = 209, SIGMA = 2;
const int L = 109, MOD = 1000000007;
char s1[L], s2[L];
int l1, l2;
int f[2][L][MAXL][4];

struct AC{
    int cnt, ch[MAXL][SIGMA], fail[MAXL], last[MAXL];
    bool end[MAXL];
    DATA val[MAXL];
    AC(){
        clear();
    }
    void clear(){
        cnt = 1; 
        end[0] = false;
        memset(ch[0], 0, sizeof(ch[0]));
    }
    int idx(char c){
        if(c == 'D') return 0;
        return 1;
    }
    void insert(const char *s, int n, DATA value){
        int now = 0;
        for(int c, i = 0; i < n; i++, now = ch[now][c]){
            c = idx(s[i]);
            if(ch[now][c] == 0){
                memset(ch[cnt], 0, sizeof(ch[cnt]));
                end[cnt] = false;
                ch[now][c] = cnt++;
            }
        }
        end[now] = true; val[now] = value;
    }
    void get_fail(){
        queue<int> q;
        fail[0] = 0;
        for(int c = 0; c < SIGMA; c++){
            int u = ch[0][c];
            if(u != 0){
                fail[u] = last[u] = 0;
                q.push(u);
            }
        }
        while(!q.empty()){
            int x = q.front(); q.pop();
            for(int c = 0; c < SIGMA; c++){
                int &y = ch[x][c];
                if(y == 0) y = ch[fail[x]][c];
                else{
                    fail[y] = ch[fail[x]][c];
                    last[y] = end[fail[y]] ? fail[y] : last[fail[y]];
                    q.push(y);
                }
            }
        }
    }
    int msk(int x){
        int ret = (end[x] ? val[x] : 0);
        if(last[x] != 0) ret |= msk(last[x]);
        return ret;
    }
}ac;

int main(){
    int cs, X, Y;
    scanf("%d", &cs);
    while(cs--){
        ac.clear();
        scanf("%d %d", &Y, &X);
        scanf("%s %s", s1, s2);
        l1 = strlen(s1); l2 = strlen(s2);
        ac.insert(s1, l1, 1);
        ac.insert(s2, l2, 2);
        ac.get_fail();
        memset(f, 0, sizeof(f));
        f[0][0][0][0] = 1;
        int s = 0;
        for(int i = 0; i <= X; i++){
            memset(f[s^1], 0, sizeof(f[s^1]));
            for(int j = 0; j <= Y; j++){
                for(int k = 0; k < ac.cnt; k++){
                    for(int m = 0; m < 4; m++) if(f[s][j][k][m] != 0){
                        int F = f[s][j][k][m];
                        int son = ac.ch[k][0];
                        f[s ^ 1][j][son][m | ac.msk(son)] += F;
                        f[s ^ 1][j][son][m | ac.msk(son)] %= MOD;
                        son = ac.ch[k][1];
                        f[s][j + 1][son][m | ac.msk(son)] += F;
                        f[s][j + 1][son][m | ac.msk(son)] %= MOD;
                    }
                }
            }
            s ^= 1;
        }
        int ans = 0;
        for(int k = 0; k < ac.cnt; k++){
            ans += f[s ^ 1][Y][k][3];
            ans %= MOD;
        }
        printf("%d\n", ans);
    }
    return 0;
}