#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

struct mint {
    static constexpr int MOD = 998244353;

    static constexpr mint pow(mint base, long exp) {
        mint ans = 1;
        while (exp) {
            if (exp & 1) {
                ans *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return ans;
    }

    static constexpr int norm(long x) {
        x %= MOD;
        if (x < 0) {
            x += MOD;
        }
        return int(x);
    }

    int x;

    constexpr mint() : x(0) {}
    constexpr mint(long x) : x(norm(x)) {}

    static constexpr mint from_unchecked(int x) {
        mint m;
        m.x = x;
        return m;
    }

    friend ostream& operator<<(ostream& out, mint m) {
        return out << m.x;
    }

    mint operator-() const {
        if (!x) {
            return 0;
        }
        return from_unchecked(MOD - x);
    }

    mint& operator+=(const mint& m) {
        x += m.x;
        if (x >= MOD) {
            x -= MOD;
        }
        return *this;
    }
    mint& operator-=(const mint& m) {
        return *this += -m;
    }

    mint& operator*=(const mint& m) {
        x = int(long(x) * m.x % MOD);
        return *this;
    }

    friend mint operator+(mint a, const mint& b) {
        return a += b;
    }
    friend mint operator-(mint a, const mint& b) {
        return a -= b;
    }
    friend mint operator*(mint a, const mint& b) {
        return a *= b;
    }
};

int n, kv;
string s;
map<vector<int>, mint> memo[100];

mint dp(int ind, const vector<int>& state) {
    if (ind > n + kv) {
        return 0;
    }
    auto [it, inserted] = memo[ind].emplace(state, 0);
    mint& ans = it->second;
    if (!inserted) {
        return ans;
    }
    if (state[n] == kv) {
        ans += 1;
    }
    for (char c = 'A'; c <= 'Z'; c++) {
        vector<int> ndp(n + 1);
        for (int i = 0; i <= n; i++) {
            ndp[i] = state[i] + 1;
            if (i) {
                ndp[i] = min(
                    {ndp[i], ndp[i - 1] + 1, state[i - 1] + 1 - (s[i - 1] == c)});
            }
        }
        ans += dp(ind + 1, ndp);
    }
    return ans;
}

void solve() {
    cin >> s >> kv;
    n = sz(s);
    cout << dp(0, ({
                   vector<int> v(n + 1);
                   iota(begin(v), end(v), 0);
                   v;
               }))
         << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}