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

#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define mkp make_pair
#define debug(x) cout << #x << " = " << x << "\n";

int rd() {
	int x = 0, f = 1;
	char ch = getchar();
	while (!('0' <= ch && ch <= '9')) {
		if (ch == '-') f = -1; ch = getchar();
	}
	while ('0' <= ch && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();
	}
	return x * f;
}

void wr(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x >= 10) wr(x / 10); putchar(x % 10 + '0');
}
bool MemoryST;

const int N = 50010;
const int M = (1 << 6) + 10;
const int mod = 1e9 + 7; 

string s;
int k;
int p[N], q[N]; 
int f[N][M][5]; pii g[M][M * 2][5];

void Add (int &x, int y) {
	x += y; if (x >= mod) x -= mod;
}

pii solve (int s, int t, int a) {
	p[6] = a; q[6] = a + 1; 
	for (int i = 5; i >= 0; --i)
		p[i] = ((s >> i) & 1) + p[i + 1];
	for (int i = 0; i < 6; ++i) q[i] = p[i + 1] + 1;
	for (int i = 0; i < 7; ++i)
		if ((t >> i) & 1) q[i] = p[i]; 
	for (int i = 1; i <= 6; ++i) q[i] = min(q[i], q[i - 1]);
	int nxts = 0;
	for (int i = 0; i < 6; ++i) nxts |= ((1 << i) * (q[i] - q[i + 1]));
	return mkp(nxts, q[6]);
}

void Mainsolve() {
	cin >> s >> k;
	int n = s.size(); s = " " + s;
	for (int s = 0; s < (1 << 6); ++s)
		for (int t = 0; t < (1 << 7); ++t)
			for (int a = 0; a <= 3; ++a)
				g[s][t][a] = solve(s, t, a);
	f[0][0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		int c = 0; 
		for (int a = 0; a < 26; ++a) {
			int st = 0;	 
			for (int j = i - 3; j <= i + 3; ++j)
				if (1 <= j && j <= n && s[j] == a + 'A')
					st |= (1 << (j - i + 3));
			if (!st) { ++c; continue; }
			for (int s = 0; s < (1 << 6); ++s)
				for (int p = 0; p <= 3; ++p)
					Add(f[i][g[s][st][p].fi][g[s][st][p].se], f[i - 1][s][p]);
		}
		int st = 0;
		for (int s = 0; s < (1 << 6); ++s)
			for (int p = 0; p <= 3; ++p)
				Add(f[i][g[s][st][p].fi][g[s][st][p].se], 1ll * f[i - 1][s][p] * c % mod);
//		debug(i);
//		for (int s = 0; s < (1 << 6); ++s)
//			for (int p = 0; p <= 3; ++p)
//				if (f[i][s][p]) cout << s << " " << p << " " << f[i][s][p] << "\n"; 
	}
	int sum = 0;
	for (int s = 0; s < (1 << 6); ++s) {
		for (int a = 0; a <= 3; ++a) {
			if (a <= k)
				Add(sum, f[n][s][a]);
		}
	}
	cout << sum << "\n";
}

bool MemoryED;
int main() {
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 

	cerr << fixed << setprecision(6) << (&MemoryST - &MemoryED) / 1024.0 << "KB\n";

	int T = 1; //cin >> T;
	while (T--) Mainsolve();

	cerr << endl << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";

//	system("fc .out .out");
	return 0;
}