#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
ll solve(string &s,ll i,ll j,ll k,vector<vector<vector<ll>>> &dp){
    if(k == 0) return 1;
    if(i > j) return 0;
 
    if(dp[i][j][k] != -1){
        return dp[i][j][k];
    }
 
    if(k == 1){
        return dp[i][j][k] = j - i + 1;
    }
 
    ll ans = 0;
 
    if(i < j && s[i] == s[j]){
        ans = solve(s,i+1,j-1,k-2,dp);
    }
 
    ans += solve(s,i+1,j,k,dp) + solve(s,i,j-1,k,dp) - solve(s,i+1,j-1,k,dp);
 
    return dp[i][j][k] = ans;
}
 
int main(){
    string s;
    cin>>s;
 
    ll k;
    cin>>k;
 
    ll n = s.length();
 
    vector<vector<vector<ll>>> dp(n,vector<vector<ll>>(n,vector<ll>(k+1,-1)));
 
    ll ans = solve(s,0,n-1,k,dp);
 
    cout<<ans<<endl;
return 0;
}
 
 
 
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGxsIGxvbmcgbG9uZwoKbGwgc29sdmUoc3RyaW5nICZzLGxsIGksbGwgaixsbCBrLHZlY3Rvcjx2ZWN0b3I8dmVjdG9yPGxsPj4+ICZkcCl7CiAgICBpZihrID09IDApIHJldHVybiAxOwogICAgaWYoaSA+IGopIHJldHVybiAwOwoKICAgIGlmKGRwW2ldW2pdW2tdICE9IC0xKXsKICAgICAgICByZXR1cm4gZHBbaV1bal1ba107CiAgICB9CgogICAgaWYoayA9PSAxKXsKICAgICAgICByZXR1cm4gZHBbaV1bal1ba10gPSBqIC0gaSArIDE7CiAgICB9CgogICAgbGwgYW5zID0gMDsKCiAgICBpZihpIDwgaiAmJiBzW2ldID09IHNbal0pewogICAgICAgIGFucyA9IHNvbHZlKHMsaSsxLGotMSxrLTIsZHApOwogICAgfQogICAgCiAgICBhbnMgKz0gc29sdmUocyxpKzEsaixrLGRwKSArIHNvbHZlKHMsaSxqLTEsayxkcCkgLSBzb2x2ZShzLGkrMSxqLTEsayxkcCk7CgogICAgcmV0dXJuIGRwW2ldW2pdW2tdID0gYW5zOwp9CgppbnQgbWFpbigpewogICAgc3RyaW5nIHM7CiAgICBjaW4+PnM7CgogICAgbGwgazsKICAgIGNpbj4+azsKCiAgICBsbCBuID0gcy5sZW5ndGgoKTsKCiAgICB2ZWN0b3I8dmVjdG9yPHZlY3RvcjxsbD4+PiBkcChuLHZlY3Rvcjx2ZWN0b3I8bGw+PihuLHZlY3RvcjxsbD4oaysxLC0xKSkpOwoKICAgIGxsIGFucyA9IHNvbHZlKHMsMCxuLTEsayxkcCk7CgogICAgY291dDw8YW5zPDxlbmRsOwpyZXR1cm4gMDsKfQoKCgo=