// 
#include <bits/stdc++.h>
#define int long long
#define vc vector <int> 
#define vcp vector <pii> 
#define pii pair <int, int> 
#define pb push_back
#define fi first
#define se second
#define O(i, l, r) for(int i = l;i <= r; ++i)
#define J(i, r, l) for(int i = r;i >= l; --i)

using namespace std; int read();
const int N = 1e5 + 5, M = 35, base = 131, Mod = 23333333377;

int K, n, m, pa[N], pb[N], mul[N];
string a, b;

void ckmax(int &x, int y) { x = max(x, y); }

int get(int l, int r, int op) {
	if(op) return (pa[r] - (__int128)pa[l - 1] * mul[r - l + 1] % Mod + Mod) % Mod;
	return (pb[r] - (__int128)pb[l - 1] * mul[r - l + 1] % Mod + Mod) % Mod;
}
int lcp(int a1, int a2) {
	if(a1 <= 0 or a2 <= 0 or a1 > n or a2 > m or a[a1] != b[a2]) return 0;
	int l = 1, r = min(n - a1 + 1, m - a2 + 1);
	while(l < r) {
		int mid = l + r + 1>> 1;
		if(get(a1, a1 + mid - 1, 1) == get(a2, a2 + mid - 1, 0)) l = mid;
		else r = mid - 1;
	} return l;
}

int f[M][M<<1], ans[N];
void one(int st) { // 钦定对 a 操作，看能匹配到 b 哪里 
	memset(f, 0xf3, sizeof f); f[0][K] = 0;
	for(int i = 0;i <= K; ++i)
		for(int j = -i;j <= i; ++j) { 
			ckmax(f[i][j + K], f[i][j + K] + lcp(f[i][j + K] + 1, f[i][j + K] + j + st));
			if(i == K) continue ; // add 和 del 的都是 f(i, j) 的基础上 
			ckmax(f[i + 1][j + 1 + K], f[i][j + K]); // add
			if(j - 1 + K >= 0) ckmax(f[i + 1][j - 1 + K], min(n, f[i][j + K] + 1)); 
				// del，本质上是给 f(i,j) 这个点完成了匹配，但是你还是要让前面的点能匹配完 j 
			ckmax(f[i + 1][j + K], min(n, f[i][j + K] + 1)); // change
		}
	for(int j = -K;j <= K; ++j) // [1, f] 匹配 [st, st + f + j] 
		for(int i = 0;i <= K; ++i) {
			if(f[i][j + K] >= n and st + j + f[i][j + K] - 1 <= m) {
//				cout << st << " " << i << " " << j << "\n";
				ans[i] ++;
				break ;
			}
		}
}

void solve() {
	cin >> K;
	cin >> a >> b; n = a.size(), m = b.size(); mul[0] = 1; a = " " + a, b = " " + b;
	for(int i = 1;i <= n; ++i) pa[i] = (pa[i - 1] * base + a[i]) % Mod;
	for(int i = 1;i <= m; ++i) mul[i] = mul[i - 1] * base % Mod, pb[i] = (pb[i - 1] * base + b[i]) % Mod;
	
//	for(int i = 1;i <= n; ++i) for(int j = 1;j <= m; ++j) cout << i << " " << j << " " << lcp(i, j) << "\n"; 
	
	for(int st = 1;st <= m; ++st) one(st);
	
	int rs = 0; for(int i = 0;i <= K; ++i) rs += ans[i];
	cout <<rs << "\n";
}	

signed main() {
	int T = 1;
//	cin >> T;
	while(T--) solve();
	return 0;
}

/*
f(i, j) 表示进行 i 次操作，for S
[1, fij] of S 匹配了 [1, fij + j] of T，当然最大化 f 
*/

int read() {
	char c; int sum = 0, f = 1; while(c < '0' or c > '9') { if(c=='-')f=-1; c = getchar(); }
	while(c >= '0' and c <= '9') sum = (sum << 3) + (sum << 1) + (c ^ 48), c = getchar();
	return sum * f;	
}