# include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
typedef vector<int> State;
int n,d,tot,f[1000010],du[1000010],trans[1000010][26];
State st[1000010];
queue<int> que;
map<State,int> mp;
char s[20];
void upd(int &a,int b){(a+=b)>=mod?a-=mod:0;}
void dfs(int u)
{
	State S=st[u];
	for(int c=0;c<26;c++)
	{
		State T(n+1);
		for(int i=0;i<=n;i++) T[i]=S[i]+1;
		for(int i=1;i<=n;i++) T[i]=min(T[i],S[i-1]+(s[i]!=c+'A'));
		for(int i=1;i<=n;i++) T[i]=min(T[i],T[i-1]+1);
		bool ok=0;
		for(int i=0;i<=n;i++) ok|=(T[i]<=d);
		if(!ok) continue;
		if(mp.count(T)) trans[u][c]=mp[T];
		else st[++tot]=T,trans[u][c]=mp[T]=tot,dfs(tot);
	}
}
int main()
{
	int ans=0;
	scanf("%s%d",s+1,&d);n=strlen(s+1);
	State S(n+1);
	for(int i=1;i<=n;i++) S[i]=i;
	tot=mp[S]=1;st[1]=S;dfs(1);
	f[1]=1;
	for(int i=1;i<=tot;i++)
		for(int j=0;j<26;j++)
			if(trans[i][j]) du[trans[i][j]]++;
	que.push(1);
	while(!que.empty())
	{
		int u=que.front(),v;que.pop();
		for(int i=0;i<26;i++)
			if((v=trans[u][i])>0)
			{
				upd(f[v],f[u]);
				if(!(--du[v])) que.push(v);
			}
	}
	for(int i=1;i<=tot;i++)
		if(st[i][n]==d) upd(ans,f[i]);
	cout<<ans<<endl;
	return 0;
}