#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=6e6+10;
int mod=1;
int n,m;
char s1[maxn];
char s2[maxn];
int nxt[maxn];
int fw[maxn];
int fr[maxn];
int sum1[maxn];
int sum2[maxn];
int p[maxn];
int ans=0;
void getnxt()
{
	int j=0;
	for(int i=2;i<=m;i++)
	{
		while(j!=0&&s2[i]!=s2[j+1]) j=nxt[j];
		if(s2[i]==s2[j+1]) j++;
		nxt[i]=j;
	}
}
void kmp()
{
	int j=0;
	for(int i=1;i<=n;i++)
	{
		while(j!=0&&s1[i]!=s2[j+1]) j=nxt[j];
		if(s1[i]==s2[j+1]) j++;
		if(j==m)
		{
			j=nxt[j];
			fw[i-m+1]=1;
			fr[i]=1;
		}
	}
}
signed main()
{
	for(int i=1;i<=32;i++)
	{
		mod*=2;
	}
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>s1[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>s2[i];
	}
	getnxt();
	kmp();
	for(int i=1;i<=n;i++)
	{
		sum1[i]=sum1[i-1]+fw[i];
		sum2[i]=sum2[i-1]+fr[i];
	}
	for(int i=1,r=0,mid=0;i<=n;i++)
	{
		if(i<=r) p[i]=min(r-i+1,p[(mid<<1)-i]);
		while(i>=p[i]&&s1[i-p[i]]==s1[i+p[i]])
		{
			++p[i];
			if(p[i]*2-1>=m) 
			{
				ans+=min((sum1[i+p[i]-1]-sum1[i-p[i]]),(sum2[i+p[i]-1]-sum2[i-p[i]]));	
				ans%=mod;	
			}
		} 
		if(p[i]+i>r) r=p[i]+i-1,mid=i;	
	}
	cout<<ans;
	return 0;
}