//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const int mod=1e9+7;
string s;
int n,k;
int _f[50005][5][5][5][5];
int f(int p,int a,int b,int c,int d)
{
	a=min(a,4);
	b=min(b,3);
	c=min(c,2);
	d=min(d,1);
	if(p==n)
	{
		if((k==0?a:(k==1?b:(k==2?c:d)))<=0) return 1;
		return 0;
	}
	if(~_f[p][a][b+1][c+2][d+3]) return _f[p][a][b+1][c+2][d+3];
	auto getch=[&](int x,int v,char ch)
	{
		while(x+v<n&&s[x+v]!=ch&&v<=4) v++;
		return v;
	};
	ll ans=0;
	for(auto ch='A';ch<='Z';ch++)
		ans+=f(p+1,getch(p,a,ch),min(a-1,getch(p,b,ch)),min(b-1,getch(p,c,ch)),min(c-1,getch(p,d,ch)));
	return _f[p][a][b+1][c+2][d+3]=ans%mod;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(_f,-1,sizeof(_f));
	cin>>s>>k;
	n=sz(s);
	cout<<f(0,0,0,0,0)<<'\n';
	return 0;
}