#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define pr pair
#define f first
#define s second
#define ll long long
#define mp make_pair
#define pll pr<ll,ll>
#define pii pr<int,int>
#define piii pr<int,pii>
using namespace std;
int tg[792],t;
int id[1<<12];
int go[792][128];
int dp[7];
ll dv[792];
ll nx[792];
const ll m=1e9+7;
int main()
{
	ios_base::sync_with_stdio(0);
	int n,w;
	string s;
	cin>>s>>w;
	n=s.size();
	int rw=w*2+1,vl=w+1;
	int l=rw+vl;
	for(int i=0;i<1<<l;i++)
	{
		int c=0;
		for(int j=0;j<l;j++) if(i&1<<j) c++;
		if(c==vl)
		{
			id[i]=t;
			tg[t++]=i;
		}
	}
	for(int fc=0;fc<t;fc++) for(int j=0;j<1<<rw;j++)
	{
		int i=tg[fc];
		int cv=0,z=0;
		for(int k=0;k<l;k++)
		{
			if(i&1<<k) cv++;
			else dp[z++]=cv;
		}
		for(int k=rw-1;k>=0;k--)
		{
			int fd=dp[k]+1;
			if(j&1<<k) fd--;
			if(k) fd=min(fd,dp[k-1]+1);
			if(k<rw-1) fd=min(fd,dp[k+1]);
			fd=min(fd,vl);
			dp[k]=fd;
		}
		cv=0;
		z=0;
		int rs=0;
		for(int i=0;i<rw;i++)
		{
			while(cv<dp[i]) rs+=1<<(z++),cv++;
			z++;
		}
		while(cv<vl) rs+=1<<(z++),cv++;
		bitset<5> r=rs;
		go[fc][j]=id[rs];
	}
	int st=id[(1<<(w*2+2))-(1<<(w+1))];
	dv[st]=1;
	for(int i=0;i<n;i++)
	{
		int ep=0;
		for(int j=0;j<t;j++) nx[j]=0;
		for(char c='A';c<='Z';c++)
		{
			int fj=0;
			for(int j=-w;j<=w;j++)
			{
				if(i+j<0||i+j>=n) continue;
				if(s[i+j]==c) fj+=1<<(w-j);
			}
			if(fj==0)
			{
				ep++;
				continue;
			}
			for(int j=0;j<t;j++) nx[go[j][fj]]+=dv[j];
		}
		for(int j=0;j<t;j++) nx[go[j][0]]+=dv[j]*ep;
		for(int j=0;j<t;j++) dv[j]=nx[j]%m;
	}
	ll ans=0;
	for(int fc=0;fc<t;fc++)
	{
		int i=tg[fc];
		int cv=0,z=0;
		for(int k=0;k<l;k++)
		{
			if(i&1<<k) cv++;
			else dp[z++]=cv;
		}
		bitset<12> b=tg[fc];
		if(dp[w]<=w) ans+=dv[fc];
	}
	cout<<ans%m<<endl;
	return 0;
}