#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 5, P = 1e9 + 7;

int f[N][4][1 << 6], g[8], tg[8];

signed main() {
    string S; cin >> S;
    int n = S.size(), m; scanf("%d", &m);
    if (!m) return 0 & puts("1");
    f[0][m][(1 << m) - 1] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= m; ++j) {
            for (int k = 0; k < 1 << (m + m); ++k) {
                if (!f[i][j][k]) continue;
                g[0] = i - m - m + j;
                for (int l = 1; l <= m + m + 1; ++l) g[l] = g[l - 1] + ((k >> (l - 1)) & 1);
                bool vis[26];
                memset(vis, 0, sizeof(vis));
                for (int l = 0; l <= m + m + 1; ++l) {
                    int t = i - m + l;
                    if (t >= 1 && t <= n) vis[S[t - 1] - 'A'] = 1;
                }
                string S1, S2;
                for (int l = 0; l < 26; ++l) {
                    if (vis[l]) S1 += (char)(l + 'A');
                    else S2 += (char)(l + 'A');
                }
                S1 += S2.back();
                for (auto c : S1) {
                    for (int l = 0; l <= m + m + 1; ++l) tg[l] = g[l];
                    for (int l = 0; l <= m + m + 1; ++l) {
                        int t = i - m + l;
                        if (t >= 1 && t <= n && S[t - 1] == c) tg[l] = max(tg[l], (l ? g[l - 1] : 0) + 1);
                    }
                    for (int l = 1; l <= m + m + 1; ++l) tg[l] = max(tg[l], tg[l - 1]);
                    if (tg[1] - (i + 1 - m) + m < 0) continue;
                    int sta = 0;
                    for (int l = 2; l <= m + m + 1; ++l) sta |= (tg[l] - tg[l - 1]) << (l - 2);
                    auto add = [&](int &x, int y) {
                        ((x += y) >= P) && (x -= P);
                    };
                    add(f[i + 1][tg[1] - (i + 1 - m) + m][sta], 1ll * f[i][j][k] * (c == S2.back() ? S2.size() : 1) % P);
                }
            }
        }
    }
    int res = 0;
    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j < 1 << (m + m); ++j) {
            if (i + __builtin_popcount(j) >= m) ((res += f[n][i][j]) >= P) && (res -= P);
        }
    }
    printf("%d\n", res);
    return 0;
}