#include <bits/stdc++.h>
#define ll long long
//#define int long long
using namespace std;

const int mod = 998244353;
const int maxn = 12;
const int mask = 60005;
inline void add(int &a,const int &b){ a+=b; if(a>=mod)a-=mod; }

int n,D;
int a[maxn],pw[12];
int f[22][mask];

void dpnh(int h[],int c,int nh[])
{
	nh[0]=h[0]+1;
	for(int i=1;i<=n;i++)
	{
		nh[i]= min( min( nh[i-1]+1,h[i]+1 ),h[i-1]+(a[i]!=c) );
	}
}
void geth(int L,int s,int h[])
{
	h[0]=L;
	for(int i=1;i<=n;i++)
	{
		int c= s/pw[i-1]%3;
		if(c==1) c=-1;
		else if(c==2) c=1;
		h[i]=h[i-1]+c;
	}
}
int getcode(int h[])
{
	int s=0;
	for(int i=1;i<=n;i++)
	{
		int c=h[i]-h[i-1];
		if(c==-1) s+= pw[i-1];
		else if(c==1) s+=pw[i-1]*2;
	}
	return s;
}
int h[maxn],nh[maxn];

//vector< pair<int,int> >cand;
//int use[50];

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	pw[0]=1; for(int i=1;i<maxn;i++) pw[i]=pw[i-1]*3;
	
	string str; cin>>str;
	n=str.size(); str=' '+str;
	for(int i=1;i<=n;i++) a[i]=str[i]-'A'+1;
	cin>>D;
	
	/*
	0 : 0
	1 : -1
	2 : 1
	*/
	
	/*
	for(int i=1;i<=n;i++) if(!use[a[i]])
	{
		cand.emplace_back(a[i],1);
		use[a[i]]=1;
	}
	{
		int num=0,las=0;
		for(int i=1;i<=26;i++) if(!use[i])
		{
			num++; las=i;
		}
		cand.emplace_back(
	}*/
	
	int S=0;
	for(int i=1;i<=n;i++) S+=2*pw[i-1];
	f[0][S]=1;
	
	int ans=0;
	int mxS=pw[n];
	for(int L=0;L<=n+D;L++)
	{
		for(int s=0;s<mxS;s++) if(f[L][s])
		{
			geth(L,s,h);
			if(h[n]==D) add(ans,f[L][s]);
			
			if(L<n+D)
			{
				for(int c=1;c<=26;c++)
				{
					dpnh(h,c,nh);
					int ns=getcode(nh);
					add(f[L+1][ns],f[L][s]);
				}
			}
		}
	}
	cout<<ans<<endl;
	
	return 0;
}