#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,mod=998244353;
int n,d,m=1,ans;
string s;
int f[N],pref[N];
int Gy[22][N];//Gy下标代表压的f数组 值代表有多少符合的串T 
int main(){
	cin>>s>>d;
	n=s.length();
	s=' '+s;
	for(int i=1;i<=n;i++) m*=3;
	Gy[0][m-1]=1;//一开始T为空 意味着S必须全删了 f随S长度变化递增1 
	for(int i=0;i<=n+d;i++){//T.len
		pref[0]=i;//一开始S前缀为空意味着需要把T整个删掉
		f[0]=i+1;
		for(int j=0;j<m;j++){//T.f的值 
			if(!Gy[i][j]) continue;			
			for(int k=1,tmp=j;k<=n;k++){//把f值拿出来 
				pref[k]=pref[k-1]+tmp%3-1;
				tmp/=3;
			}
			if(pref[n]==d) ans=(ans+Gy[i][j])%mod;
			for(int c=0;c<26;c++){//枚举新串用T转移 
				int p=0;
				for(int k=1,tmp=1;k<=n;k++){
					f[k]=min(pref[k]+1,min(pref[k-1]+((s[k]-'A')!=c),f[k-1]+1));
					p+=tmp*(f[k]-f[k-1]+1);
					tmp*=3;
				}
				Gy[i+1][p]=(Gy[i+1][p]+Gy[i][j])%mod;
			} 
			
		}
	}
	cout<<ans;
	return 0;
}