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

const int MN = 11, MOD = 119<<23|1, MC = 26, MD = 59049;
inline void add(int &x, int v) { x += v-MOD; x += x>>31 & MOD; }

int N, D, ar[MN], tmp[MN], tmpN[MN], dpPv[MD], dpCur[MD]; string s;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  cin >> s >> D; N = s.size();
  for (int i = 0; i < N; i++)
    ar[i] = s[i]-'A';
  int pw = 1;
  for (int i = 0; i < N; i++)
    pw *= 3;
  dpPv[pw-1] = 1;
  int ans = 0;
  for (int l = 0; l <= N+D; l++) {
    tmp[0] = l; tmpN[0] = l+1;
    memset(dpCur, 0, sizeof dpCur);
    for (int msk = 0; msk < pw; msk++) {
      if (!dpPv[msk]) continue;
      for (int i = 1, m = msk; i <= N; i++)
        tmp[i] = tmp[i-1] + m%3 - 1,
        m /= 3;
      if (tmp[N] == D) add(ans, dpPv[msk]);
      for (int z = 0; z < MC; z++) {
        int m1 = 0;
        for (int i = 1, p = 1; i <= N; i++)
          tmpN[i] = min({tmp[i] + 1, tmpN[i-1] + 1, tmp[i-1] + (z != ar[i-1])}),
          m1 += p * (tmpN[i] - tmpN[i-1] + 1),
          p *= 3;
        add(dpCur[m1], dpPv[msk]);
      }
    }
    memcpy(dpPv, dpCur, sizeof dpPv);
  }
  printf("%d\n", ans);

  return 0;
}