#include<bits/stdc++.h> #define int long long using namespace std; const int N=111,M=2000,P=998244353; int n,m,len,ans,dp[M][N],f[N][N][N]; string s,p,t; int qpow(int x,int y) { if(y==0)return 1; int z=qpow(x,y/2); if(y%2)return z*z%P*x%P; return z*z%P; } int C(int x,int y) { if(y>x)return 0; int z=1; while(y) { z=z*x%P*qpow(y,P-2)%P; --y; --x; } return z; } signed main() { //freopen("curse.in","r",stdin); //freopen("curse.out","w",stdout); int flag=1; cin>>n>>m>>s>>p; for(int i=1;i<m;i++) { if(p[i-1]!=p[i]) { flag=0; } } if(flag) { int sum=0; for(int i=1;i<=n;i++) { sum*=2; if(s[i-1]==p[0]) { sum++; } sum%=P; //cout<<sum<<"\n"; } cout<<C(sum,m); return 0; } if(n<=10&&m<=10) { for(int i=1;i<=n;i++) { t=t+s[i-1]+t; len=len*2+1; } dp[0][0]=1; for(int i=1;i<=m;i++) { int sum=0; sum+=dp[0][i-1]; for(int j=1;j<=len;j++) { if(t[j-1]==p[i-1]) { dp[j][i]=sum; } sum=(sum+dp[j][i-1])%P; //cout<<f[j][i]<<' '; } //cout<<'\n'; } for(int i=1;i<=len;i++) { ans=(ans+dp[i][m])%P; } cout<<ans<<"\n"; return 0; } s='#'+s; p='#'+p; for(int i=1;i<=n;i++) { for(int len=1;len<=m;len++) { for(int l=1,r=len;r<=m;l++,r++) { if(len==1&&s[i]==p[l]) { f[i][l][r]++;//来自单个Si f[i][l][r]%=P; } f[i][l][r]+=f[i-1][l][r]*2;//来自单个Ti f[i][l][r]%=P; for(int k=l;k<r;k++) { f[i][l][r]+=f[i-1][l][k]*f[i-1][k+1][r];//来自两个Ti f[i][l][r]%=P; } if(s[i]==p[r]) { f[i][l][r]+=f[i-1][l][r-1];//来自Ti+Si f[i][l][r]%=P; } if(s[i]==p[l]) { f[i][l][r]+=f[i-1][l+1][r];//来自Si+Ti f[i][l][r]%=P; } for(int k=l+1;k<r;k++) { if(p[k]==s[i]) { f[i][l][r]+=f[i-1][l][k-1]*f[i-1][k+1][r];//来自Ti+Si+Ti f[i][l][r]%=P; } } f[i][l][r]%=P; } } } cout<<f[n][1][m]<<"\n"; return 0; }