#include <bits/stdc++.h>
#define MOD 1000000007
int N,K,kk,vc[50009][509];
char s[50009];
std::unordered_map<long long,int> id;
int sv(int x,std::vector<int> y) {
	if(y.size()>=K+2&&y[K+1]<=x) {
		return 0;
	}
    if(x==N) {
        return 1;        
    }
	while(y.size()>K+2) {
		y.pop_back();
	}
	for(int i=std::min((signed)y.size()-1,K);i>=1;i--) {
		if(y[i]<x+i-K-1) {
			y[i]=x+i-K-1;
		}
	}
    long long aa=y.size();
    for(int i=1;i<y.size();i++) {
    	aa=(aa*137ll+y[i]-(x-K)+17)%10000000000000061ll;
    }
    if(!id[aa]) id[aa]=++kk;
    aa=id[aa];
    if(vc[x][aa]!=-1) return vc[x][aa];
    int ans=0,as=0;
    for(int j=1;j<y.size();j++) {
    	as|=(1<<(s[y[j]]-'A'));
    }
    if(x+K+1<=N) {
    	as|=(1<<s[x+K+1]-'A');
    }
    for(int i=0;i<26;i++) {
        if((as>>i)&1) {
    	    std::vector<int> z=y;
	        if(x+K+1<=N) z.push_back(x+K+1);
        	for(int j=z.size()-1;j>=1;j--) {
        		int x=z[j],ff=0;
        		if(s[x]==i+'A') {
        			int le=j;
        			while(le+1<z.size()&&z[le+1]==z[le]+1) {
        				le++;
        			}
        			for(int k=j;k<=le;k++) z[k]++;
    	    	}
	        }
    	    if(z[z.size()-1]>std::min(x+K+1,N)) z.pop_back();
	       	ans=(ans+sv(x+1,z))%MOD;
    	}
    }
    if(as!=(1<<26)-1) {
    	as=26-__builtin_popcount(as);
        if(x+K+1<=N) y.push_back(x+K+1);
        ans=(ans+1ll*as*sv(x+1,y))%MOD;
    }
    vc[x][aa]=ans;
    return ans;
}
signed main(void) {
//	freopen("conquer.in","r",stdin);
//	freopen("conquer.out","w",stdout);
	//for(int i=1;i<=100;i++) s[i]=rand()%26+'A';
	memset(vc,-1,sizeof(vc));
    scanf("%s",s+1);
    N=strlen(s+1);
    scanf("%d",&K);
    if(K>=N) {
        int as=1;
        for(int i=1;i<=N;i++) as*=26;
        printf("%d",as);
        return 0;
    }
	//K=3;
    if(K==0) {
    	printf("1");
    	return 0;
    }
    std::vector<int> x;
    x.push_back(0);
    for(int i=1;i<=K;i++) x.push_back(i);
    printf("%d",sv(0,x));
}