#include <bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
    int ch = 0, f = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}
const int N = 50005, mod = 1e9 + 7;
char str[N];
int dp[2][5][300], vis[100], g[10], h[10], n, k;
inline void up(int &x, int y){ x = x + y >= mod ? x + y - mod : x + y; }
inline int work(int pos, int s, char c){
    g[0] = 0;
    for(int i = 1; i <= 2 * k; i++) g[i] = ((s >> (i - 1)) & 1) + g[i-1];
    for(int i = 0; i <= 2 * k; i++){
        h[i] = 0;
        if(i) h[i] = max(h[i], h[i-1]);
        if(i + 1 <= 2 * k) h[i] = max(h[i], g[i+1]);
        int p = pos - k + 1 + i;
        if(p >= 1 && p <= n && str[p] == c)
            h[i] = max(h[i], g[i] + 1);
    }
    // cerr << "!" << h[0] << " " << c << " " << pos << endl;
    int res = 0;
    for(int i = 2 * k; i >= 0; i--){
        if(i) res = res * 2 + (h[i] - h[i-1]);
        else res = res * 2 + h[i];
    }
    return res;
}
int main(){
    scanf("%s", str + 1);
    read(k);
    n = strlen(str + 1), dp[0][k][(1<<k)-1] = 1;
    for(int i = 0; i < n; i++){ 
        int o = i & 1;
        for(int j = 0; j <= k; j++) for(int s = 0; s < (1 << (2 * k)); s++) dp[o^1][j][s] = 0;
        for(int s = 0; s < (1 << (2 * k)); s++){
            int flag = 0;
            for(int j = 0; j <= k; j++) flag |= dp[o][j][s];
            if(!flag) continue;
            // cout << i << " " << s << endl;
            vector<pair<int, int> > vec;
            int cnt = 0;
            for(int p = max(1, i - k + 1); p <= min(n, i + k + 1); p++){
                if(vis[str[p]-'A']) continue;
                vis[str[p]-'A'] = 1;
                vec.push_back({work(i, s, str[p]), 1});
                cnt++;
            }
            for(int p = max(1, i - k + 1); p <= min(n, i + k + 1); p++) vis[str[p]-'A'] = 0;

            vec.push_back({work(i, s, 'a'), 26 - cnt});
            // cout << (int) (vec.size()) << endl;
            for(int j = 0; j <= k; j++) if(dp[o][j][s]){
                for(auto [x, y] : vec){
                    int nj = j - 1 + (x & 1);
                    // cout << j << " " << nj << endl;
                    if(nj < 0) continue;
                    up(dp[o^1][nj][x>>1], (int) (1ll * dp[o][j][s] * y % mod));
                }
            }
        }
    }
    int ans = 0, o = n & 1;
    for(int j = 0; j <= k; j++)
        for(int s = 0; s < (1 << (2 * k)); s++) if(dp[o][j][s]){
            int nj = j;
            for(int p = 0; p < k; p++) nj += (s >> p) & 1;
            if(nj >= k) up(ans, dp[o][j][s]);
        }
    cout << ans << endl;
}