#include<bits/stdc++.h>
#define rep(i,a,b) for (register int i=(a);i<=(b);i++)
#define drep(i,a,b) for (register int i=(a);i>=(b);i--)
typedef long long ll;
using namespace std;

const int mod=1e9+7;
inline int qmo(int x){return x+((x>>31)&mod);}
inline int add(int x,int y){return qmo(x+y-mod);}
inline int sub(int x,int y){return qmo(x-y);}
inline void inc(int &x,int y){x=add(x,y);}
inline void dec(int &x,int y){x=sub(x,y);}
inline int quick_pow(int x,int k){int res=1; for (;k;k>>=1,x=1ll*x*x%mod) if (k&1) res=1ll*res*x%mod; return res;} 

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	
	string s; int n,k; cin>>s>>k; n=s.size(); s=" "+s;
	
	vector<array<int,26> > nxt(n+2);
	rep(i,0,25) nxt[n+1][i]=114514;
	drep(i,n,1) 
	{
		rep(j,0,25) nxt[i][j]=nxt[i+1][j]+1;
		nxt[i][s[i]-'A']=0;
	}
	
	vector<int> dp(625);
	dp[0+1*5+2*25+3*125]=1;
	rep(i,0,n-1)
	{
		vector<int> ndp(625);
		rep(S,0,624) if (dp[S]) 
		{
			array<int,4> f={S%5,S/5%5,S/25%5,S/125%5};
			rep(c,0,25)
			{
				array<int,4> g={4,f[0],f[1],f[2]};
				rep(j,0,3) if (f[j]<4) g[j]=min(g[j],f[j]+nxt[i-j+f[j]+1][c]);
				inc(ndp[g[0]+5*g[1]+25*g[2]+125*g[3]],dp[S]);
			}
		}
		swap(dp,ndp);
	}
	
	int ans=0;
	rep(S,0,624)
	{
		array<int,4> f={S%5,S/5%5,S/25%5,S/125%5};
		if (n-k+f[k]<=n) inc(ans,dp[S]); 
	}
	cout<<ans<<endl;
	
	return 0;
}