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

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << "\n";
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  string str;
  int d;
  cin >> str >> d;

  const int n = (int)str.size();

  vector<int> NDP(n + 1);

  vector<map<vector<int>, int>> dp(22);
  {
    vector<int> vv(n + 1);
    iota(all(vv), 0);
    dp[0][vv] = 1;
  }

  constexpr int mod = 998244353;
  int ans = 0;

  for (int t = 0; t <= 20; t++) {

    for (const auto &[DP, val] : dp[t]) {
      if (DP[n] == d)
        ans = (ans + val) % mod;

      for (char c = 'A'; c <= 'Z'; c++) {
        for (int i = 0; i <= n; i++) {
          NDP[i] = DP[i] + 1;
          if (i) NDP[i] = min(NDP[i], NDP[i - 1] + 1);
          if (i) {
            NDP[i] = min(NDP[i], DP[i - 1] + (c != str[i - 1]));
          }
        }

        dp[t + 1][NDP] += val;
        dp[t + 1][NDP] %= mod;
      }
    }
    debug(dp[t].size());
  }

  cout << ans << '\n';

  return 0;
}