/*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3fll
#define For(i,l,r) for(register int i=(l);i<=(r);++i)
#define Rof(i,l,r) for(register int i=(l);i>=(r);--i)
bool M_S;
const int mod=1000000007;
void add(int &x,int y){if((x+=y)>=mod) x-=mod;}
const int N=50005;
int n,m,f[2][(1<<6)][5],g[N],h[N];
char str[N];
void MAIN(){
	cin>>(str+1);n=strlen(str+1);
	cin>>m;f[0][0][0]=1;
	For(i,1,n){
		int I=i-1;
		For(s,0,(1<<(m<<1))-1) For(j,0,m) if(f[I&1][s][j]){
			g[I]=I-j;
			For(k,I+1,min(n,I+m)) g[k]=g[k-1]+((s>>((k-1)-(I-m)))&1);
			Rof(k,I-1,max(1ll,I-m)) g[k]=g[k+1]-((s>>(k-(I-m)))&1);
			for(char S='A';S<='Z';S++){
				For(k,max(1ll,i-m),min(n,i+m)) h[k]=max(max(h[k-1],g[k]),g[k-1]+(str[k]==S));
				int t=0;For(k,max(0ll,i-m),min(n,i+m)-1) if(h[k]^h[k+1]) t|=(1<<(k-(i-m)));
				add(f[i&1][t][i-h[i]],f[I&1][s][j]);
			}
			f[I&1][s][j]=0;
		}
	}
	int ans=0;
	For(s,0,(1<<(m<<1))-1) For(j,0,m) add(ans,f[n&1][s][j]);
	cout<<ans<<'\n';
}
bool M_T;
signed main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	// cerr<<"Memory: "<<1.0*(&M_S-&M_T)/1048576<<"MiB\n";
	double T_S=clock();MAIN();double T_T=clock();
	// cerr<<"Time: "<<1.0*(T_T-T_S)/CLOCKS_PER_SEC*1000<<"ms\n";
	return 0;
}