#include<bits/stdc++.h>
#define pb           push_back
#define pii          pair<int,int>
#define vi           vector<int>
#define vii         vector<pair<int,int>>
#define mp           make_pair
#define FOR(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD0(i, n) for (int i = (int)n; i >= 0; i--)
#define FORD1(i, n) for (int i = (int)n; i >= 1; i--)
#define debug(X) { cout << #X << " = " << (X) << endl; }
#define endl '\n'
#define int long long int
using namespace std;


signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    string s;cin >> s;
    int n = s.length();
    int k;cin >> k;
    vector<vi> dp(n+1, vi(n+1));
    vector<vi> prev(n+1, vi(n+1));
    for(int change = 0; change <= k; change++){
        for(int len = 1; len <= n; len++){
            for(int start =0; start <= n - len; start++){
                dp[start][len] = max(dp[start+1][len-1], dp[start][len-1]); 
                if(s[start] == s[start + len -1]){
                    dp[start][len] = max(1 + (len != 1) + dp[start+1][max(len-2,0LL)], dp[start][len]);
                }else if(change > 0){
                    dp[start][len] = max(1 + (len != 1) + prev[start+ 1][max(len-2,0LL)], dp[start][len]); 
//                cout << dp[start][len] <<  " ";
                }
            }
//            cout << endl;
        }
        swap(dp, prev);
    }
    cout << prev[0][n];
}




#include <bits/stdc++.h>
using namespace std;
#define int long long
using vec_int = vector<int>;
using P = pair<int,int>;
using T = tuple<int,int,int>;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int charToInt(char c){
    char zero_num = '0';
    return (int)c - (int)zero_num;
}

signed main(){
    int MOD = pow(10,9)+7;

    int H, W, K; cin>>H>>W>>K;
    if(W==1){
        cout<<1<<endl;
        return 0;
    }


    // 一列における棒の組み合わせをbit全探索で先に作っておく
    // [[],[0],[1],[0,2],...]
    // これの意味は0: 0-1の間, 1: 1-2の間に棒をおく、という感じである。
    
    vector<vector<int>> combi_list;
    for(int i=0;i< (1<<(W-1));i++){
        bitset<7> s(i);
        vec_int temp_combi;
        for(int i=0;i<W-1;i++){
            if(s[i]==1){
                temp_combi.push_back(i);
            }
        }
        // 作ったものが合法かをチェックする
        int prev=-100;
        int flag = 0;
        for(auto a: temp_combi){
            if(a-prev==1){
                flag=1;
                break;
            }
            prev=a;
        }
        if(flag==1)continue;

        combi_list.push_back(temp_combi);

    }
    /*
    for(auto aa: combi_list){
        cout<<"aa"<<endl;
        for(auto bb: aa){
            cout<<bb<<endl;
        }
    }
    */


    int DP[H+1][W];
    rep(i,H+1){
        rep(j,W){
            DP[i][j]=0;
        }
    }
    DP[0][0] = 1;

    for(int i=1;i<H+1;i++){
        for(int j=0;j<W;j++){
            // 最初にそのまま落ちてくるパターン
            int pattern = 0;
            for(auto aa: combi_list){
                int flag = 1;
                for(auto bb: aa){
                    if(bb==j||bb==j-1){
                        flag=0;
                        break;
                    }
                }
                if(flag==0)continue;
                pattern++;
            }
            DP[i][j] += DP[i-1][j]*pattern;

            // 一個左の棒から落ちてくるパターン
            pattern = 0;
            for(auto aa: combi_list){
                int flag = 0;
                for(auto bb: aa){
                    if(bb==j-1){
                        flag=1;
                        break;
                    }
                }
                if(flag==0)continue;
                pattern++;
            }
            if(j>0){
                DP[i][j] += DP[i-1][j-1]*pattern;
            }
            // 一個右の棒から落ちてくるパターン
            pattern = 0;
            for(auto aa: combi_list){
                int flag = 0;
                for(auto bb: aa){
                    if(bb==j){
                        flag=1;
                        break;
                    }
                }
                if(flag==0)continue;
                pattern++;
            }
            if(j<W-1){
                DP[i][j] += DP[i-1][j+1]*pattern;
            }

            DP[i][j] = DP[i][j]%MOD;
        }
    }

    cout<<DP[H][K-1]<<endl;





    return 0;
}