#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
void file_IO() {
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
const int N=1e6+5,M=15,MOD=998244353;
void add(int &a,int b) {
	a+=b;
	if(a>=MOD)
		a-=MOD;
}
map<vector<int>,int> num;
vector<int> vec[N];
char s[N];
int n,d,head[N],in[N],len,cnt;
struct node {
	int to,nxt;
}; node edge[N<<1];
void add_edge(int u,int v) {
	edge[++len]={v,head[u]}; head[u]=len; ++in[v];
}
void dfs(int u) {
	vector<int> f=vec[u];
	rep(ch,'A','Z') {
		vector<int> g(n+1);
		rep(i,0,n)
			g[i]=f[i]+1;
		rep(i,1,n)
			chkmin(g[i],f[i-1]+(s[i]!=ch));
		rep(i,1,n)
			chkmin(g[i],g[i-1]+1);
		bool flag=false;
		rep(i,1,n)
			flag|=g[i]<=d;
		if(flag) {
			if(!num.count(g)) {
				num[g]=++cnt;
				vec[cnt]=g;
				dfs(cnt);
			}
			add_edge(u,num[g]);
		}
	}
}
int f[N];
void toposort() {
	queue<int> q;
	q.push(1);
	f[1]=1;
	while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int i=head[u];i;i=edge[i].nxt) {
			int v=edge[i].to;
			add(f[v],f[u]);
			if(!--in[v])
				q.push(v);
		}
	}
}
void solve() {
	scanf("%s",s+1);
	scanf("%d",&d);
	n=strlen(s+1);
	vector<int> tmp(n+1);
	rep(i,1,n)
		tmp[i]=i;
	num[tmp]=++cnt;
	vec[cnt]=tmp;
	dfs(1);
	toposort();
	int res=0;
	rep(i,1,cnt)
		add(res,(vec[i][n]==d)*f[i]);
	printf("%d\n",res);
}
signed main() {
	//file_IO();
	int testcase=1;
	//scanf("%d",&testcase);
	while(testcase--)
		solve();
	return 0;
}