#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 5e4 + 10;
int n, m;
char S[N];
const ll P = 1e9 + 7;
int f[1<<6][4], g[1<<6][4];
int fr[N], to[N], cnt[200];
int dd = 0;

void solve(){
	f[0][0] = 1;
	for(int i = 1; i <= n; ++ i){
		memcpy(g, f, sizeof(g));
		memset(f, 0, sizeof(f));
		for(int s = 0; s < (1 << m + m); ++ s){
			for(int j = 0; j <= m; ++ j){
				fr[i-1] = i-1-j;
				for(int k = 1; k <= m; ++ k){
					if(i-1+k <= n){
						fr[i-1+k] = fr[i-1+k-1] + ((s >> (m+k-1)) & 1);
					}
					if(i-1-k >= 1){
						fr[i-1-k] = fr[i-1-k+1] - ((s >> (m-k)) & 1);
					}
				}
				int nd = 0;
				for(int k = max(1, i-m); k <= min(n, i+m); ++ k){
					cnt[S[k]] = 1; 
				}
				for(char ch = 'A'; ch <= 'Z'; ++ ch){
					if(!cnt[ch]){
						++ nd;
						continue;
					}
					for(int k = max(1, i-m); k <= min(n, i+m); ++ k){
						to[k] = max(fr[k], to[k-1]);
						if(ch == S[k]){
							to[k] = max(to[k], fr[k-1] + 1);
						}
					}
					int st = 0;
					if(i+1 <= n)           st ^= (to[i+1] - to[i]) << m;
					if(i+2 <= n && m >= 2) st ^= (to[i+2] - to[i+1]) << (m+1);
					if(i+3 <= n && m >= 3) st ^= (to[i+3] - to[i+2]) << (m+2);
					if(i >= 2)             st ^= (to[i] - to[i-1]) << (m-1);
					if(i >= 3 && m >= 2)   st ^= (to[i-1] - to[i-2]) << (m-2);
					if(i >= 4 && m >= 3)   st ^= (to[i-2] - to[i-3]) << (m-3);
					if(i - to[i] <= m){
						f[st][i-to[i]] += g[s][j];
						if(f[st][i-to[i]] >= P) f[st][i-to[i]] -= P;
					}
				}
				for(int k = max(1, i-m); k <= min(n, i+m); ++ k){
					to[k] = max(fr[k], to[k-1]);
				}
				int st = 0;
				if(i+1 <= n)           st ^= (to[i+1] - to[i]) << m;
				if(i+2 <= n && m >= 2) st ^= (to[i+2] - to[i+1]) << (m+1);
				if(i+3 <= n && m >= 3) st ^= (to[i+3] - to[i+2]) << (m+2);
				if(i >= 2)             st ^= (to[i] - to[i-1]) << (m-1);
				if(i >= 3 && m >= 2)   st ^= (to[i-1] - to[i-2]) << (m-2);
				if(i >= 4 && m >= 3)   st ^= (to[i-2] - to[i-3]) << (m-3);
				if(i - to[i] <= m)     f[st][i-to[i]] = (f[st][i-to[i]] + 1ll * g[s][j] * nd) % P;
				for(int k = max(1, i-m); k <= min(n, i+m); ++ k){
					cnt[S[k]] = 0; 
				}
				fr[i-1] = 0;
				for(int k = 1; k <= m; ++ k){
					if(i-1+k <= n){
						fr[i-1+k] = 0;
					}
					if(i-1-k >= 1){
						fr[i-1-k] = 0;
					}
				}
			}
		}
	}
	ll ans = 0;
	for(int s = 0; s < (1 << m + m); ++ s){
		for(int i = 0; i <= m; ++ i){
			ans = (ans + f[s][i]) % P;
		}
	}
	printf("%lld\n", ans);
}

int main(){
	scanf("%s", S+1);
	n = strlen(S+1);
	scanf("%d", &m);
	if(m == 0){
		puts("1");
	} else {
		solve();
	}
	return 0;
}