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

#define fi first
#define se second

const int MOD = 998244353;

inline int mod1(int x) { return x < MOD ? x : x - MOD; }
inline int mod2(int x) { return x < 0 ? x + MOD : x; }
inline void add(int &x, int y) { x = mod1(x + y); }
inline void sub(int &x, int y) { x = mod2(x - y); }

int n, d;
string s;

map<vector<int>, int> f[21];

int main() {
	cin >> s >> d;
	n = s.length();
	
	s = "@" + s; // 1-indexed
	
	vector<int> v(n + 1);
	for (int i = 0; i <= n; ++i) {
		v[i] = i;
	}
	f[0][v] = 1;
	
	for (int i = 1; i <= n + d; ++i) {
		for (map<vector<int>, int> :: iterator it = f[i - 1].begin(); it != f[i - 1].end(); ++it) {
			vector<int> olddp = (it -> fi);
			for (int c = 'A'; c <= 'Z'; ++c) {
				vector<int> newdp(n + 1);
				newdp[0] = i;
				for (int j = 1; j <= n; ++j) {
					// dp[i][j] = min{ dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (s[i] != t[j]) }
					newdp[j] = min(min(olddp[j] + 1, newdp[j - 1] + 1), olddp[j - 1] + (s[j] != c));
					if (newdp[j] > 11) {
						newdp[j] = 11;
					}
				}
				add(f[i][newdp], it -> se);
			}
		}
	}
	
	int ans = 0;
	for (int l = 0; l <= n + d; ++l) {
		for (map<vector<int>, int> :: iterator it = f[l].begin(); it != f[l].end(); ++it) {
			vector<int> dp = (it -> fi);
			if (dp[n] == d) {
				add(ans, it -> se);
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}