#include<bits/stdc++.h>
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+10,mod=998244353,inf=1e9,P=17771;
inline void Min(int &x,int y){if(x>y)x=y;}
inline void Max(int &x,int y){if(x<y)x=y;}
int K,n,m,f[35][70],ans[N];
ull hs[2][N],p[N];
char s[N],t[N];
inline int get(int l,int r,int id){return hs[id][r]-hs[id][l-1]*p[r-l+1];}
inline int LCP(int x,int y){
	if(x<0||x>n||y<0||y>m)return 0;
	int l=1,r=std::min(n-x+1,m-y+1),res=0;
	while(l<=r){
		int mid=l+r>>1;
		if(get(x,x+mid-1,0)==get(y,y+mid-1,1))l=mid+1,res=mid;
		else r=mid-1;
	}return res;
}
signed main(){
    // freopen("edit.in","r",stdin);freopen("edit.out","w",stdout);
    // freopen("in.in","r",stdin);freopen("out.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    std::cin>>K>>s+1>>t+1;n=strlen(s+1),m=strlen(t+1);
    p[0]=1;for(int i=1;i<=std::max(n,m);++i)p[i]=p[i-1]*P;
    for(int i=1;i<=n;++i)hs[0][i]=hs[0][i-1]*P+s[i]-'a'+1;
    for(int i=1;i<=m;++i)hs[1][i]=hs[1][i-1]*P+t[i]-'a'+1;
    for(int st=1;st<=m;++st){
    	for(int i=0;i<=K;++i)for(int j=0;j<=2*K;++j)f[i][j]=0;
    	f[0][K]=0;
    	for(int i=0;i<=K;++i)for(int j=-i;j<=i;++j){
    		f[i][j+K]+=LCP(f[i][j+K]+1,f[i][j+K]+st+j);
    		if(i!=K)
    			Max(f[i+1][j+K-1],std::min(f[i][j+K]+1,n)),
    			Max(f[i+1][j+K],std::min(f[i][j+K]+1,n)),
    			Max(f[i+1][j+K+1],f[i][j+K]);
    	}
    	for(int j=std::max(-K,1-n);j<=std::min(K,m-st-n+1);++j)
    		for(int i=0;i<=K;++i)if(f[i][j+K]>=n){ans[i]++;break;}
    }ll sum=0;for(int i=0;i<=K;++i)sum+=ans[i];
	std::cout<<sum<<'\n';
}