#include<bits/stdc++.h>

using namespace std;

char s[],t[];

typedef long long ll;

ll dp[][][];

ll C[][];

ll mod=;

void init()

{

    for(int i=;i<;i++){

        C[i][i]=;

        C[i][]=;

    }

    for(int i=;i<;i++){

        for(int j=i+;j<;j++){

            C[j][i]=(C[j-][i-]+C[j-][i])%mod;

        }

    }

}

int main()

{

    int T;

    int n,m;

    ll ans;

    init();

    scanf("%d",&T);

    while(T--){

        ans=;

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

        scanf("%s",s);

        scanf("%s",t);

       for(int i=;i<=max(m,n);i++)

        dp[i][][]=dp[i][][]=;

       // for(int i=0;i<=n;i++)dp[0][i]=1;

        for(int i=;i<m;i++){

            for(int j=;j<n;j++){

                dp[i+][j+][]=((dp[i][j][])*(s[i]==t[j])+dp[i][j+][])%mod;

                dp[i+][j+][]=(dp[i][j+][]+(s[i]>t[j])*dp[i][j][]+(j>)*dp[i][j][])%mod;

             //   cout<<dp[i+1][j+1][1]<<' ';

            }

           // cout<<'\n';

           // cout<<i<<" "<<ans<<'\n';

        }

        ans=dp[m][n][];

        //cout<<ans<<'\n';

        for(int k=n+;k<=m;k++)

        for(int i=;i+k-<=m;i++){

            if(s[i-]!='')

            ans=(ans+C[m-i][k-])%mod;

        }

        cout<<ans<<'\n';

    }

}