#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<62;
const int INF = 1<<30;
const double PI=acos(-1);
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {// テーブルを作る前処理
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++){
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

long long COM(int n, int k){ // 二項係数:nCk計算
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
	COMinit();
	int n,m;
	ll ans=1LL;
	cin >>n>>m;
	int bef=m;
	map<int,int>co;
	int c=0;
	for(int i=2;i<=sqrt(bef);i++){
		c=0;
		while(bef%i==0){
			bef/=i;
			c++;
		}
		if(c){
			co[i]+=0;
			co[i]+=c;
		}
	}
	if(bef!=1){
		co[bef]+=0;
		co[bef]++;
	}
	for(auto itr=co.begin();itr!=co.end();itr++){
		ans*=COM(itr->S + n-1 , n-1);
		ans%=MOD;
	}
	cout<<ans<<endl;
}
#include <bits/stdc++.h>
using namespace std;
string s;
int n, dp[305][305][305];
int go(int l, int r, int k) {
	if (dp[l][r][k] != -1) return dp[l][r][k];
	if (l == r) {
		return dp[l][r][k] = 1;
	}
	if (l + 1 == r) {
		if (s[l] == s[r] || k) {
			return dp[l][r][k] = 2;
		} else {
			return dp[l][r][k] = 1;
		}
	}
	dp[l][r][k] = max(go(l + 1, r, k), go(l, r - 1, k));
	if (s[l] == s[r]) {
		dp[l][r][k] = max(dp[l][r][k], go(l + 1, r - 1, k) + 2);
	} else if (k) {
		dp[l][r][k] = max(dp[l][r][k], go(l + 1, r - 1, k - 1) + 2);
	}
	return dp[l][r][k];
}
int main() {
	int k;
	cin >> s >> k;
	n = s.size();
	memset(dp, -1, sizeof(dp));
	cout << go(0, n - 1, k) << endl;
	return 0;
}