#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()

const int N = 2e5 + 5;
const ll M = 998244353;

void add(ll &a, ll b) {
    a = (a + b);
    if (a >= M)
        a -= M;
}

ll dp[2][N];

int hs(vector<int> &v) {
    int res = 0;
    for (int i = 1, bs = 1; i < SZ(v); i++, bs *= 3) {
        assert(abs(v[i] - v[i - 1]) <= 1);
        if (v[i] < v[i - 1])
            res += 0 * bs;
        else if (v[i] == v[i - 1])
            res += 1 * bs;
        else
            res += 2 * bs;
    }
    return res;
}

vector<int> rhs(int now, int n, int I) {
    vector<int> res;
    res.pb(now);
    for (int i = 1; i <= n; i++) {
        int x = I % 3;
        I /= 3;
        if (x == 0)
            --now;
        else if (x == 1)
            ;
        else
            ++now;
        res.pb(now);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    string s;
    int d;
    cin >> s >> d;
    int n = SZ(s);
    ll ans = 0;


    int fg = 0;
    {
        vector<int> tmp;
        for (int i = 0; i <= n; i++)
            tmp.pb(i);
        dp[0][hs(tmp)] = 1;
    }
    int C = 1;
    for (int i = 1; i <= n; i++)
        C *= 3;
    for (int kz = 1; kz <= 21; kz++) {
        fg = !fg;
        memset(dp[fg], 0, sizeof(dp[fg]));
        for (int I = 0; I < C; I++)
            if (dp[!fg][I]) {
                vector<int> cur = rhs(kz - 1, n, I);
                if (cur.back() == d)
                    add(ans, dp[!fg][I]);
                for (int j = 0; j < 26; j++) {
                    vector<int> nxt(n + 1); 
                    nxt[0] = kz;
                    for (int k = 1; k <= n; k++)
                        nxt[k] = min({nxt[k - 1] + 1, cur[k] + 1, cur[k - 1] + (j != (s[k - 1] - 'A'))});
                    add(dp[fg][hs(nxt)], dp[!fg][I]);  
                }
            }
    }
    cout << ans << endl;
}