#include <bits/stdc++.h>


using namespace std;

//#define int long long

//const long long INF = 1e18 + 7;
const int MAXN = 5000 + 10;
//const int N = 1e5 + 10;

//#define int unsigned short int

unsigned short int dp[MAXN][MAXN];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    unsigned short int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    for (unsigned short int i = 0; i < n - 1; ++i) {
        dp[i][i + 1] = (s[i] == s[i + 1] ? 0 : 1);
    }
    for (unsigned short int len = 2; len < n; ++len) {
        for (unsigned short int l = 0; l + len < n; ++l) {
            unsigned short int r = l + len;
            dp[l][r] = dp[l + 1][r - 1] + (s[l] == s[r] ? 0 : 1);
        }
    }
    for (unsigned short int i = 0; i < n - 1; ++i) {
        dp[i][i] = 1;
        dp[i][i + 1] = (dp[i][i + 1] <= k? 1 : 0) + 2;
    }
    dp[n - 1][n - 1] = 1;
    for (unsigned short int len = 2; len < n; ++len) {
        for (unsigned short int l = 0; l + len < n; ++l) {
            unsigned short int r = l + len;
            unsigned short int val = (dp[l][r] <= k ? 1 : 0);
            dp[l][r] = dp[l + 1][r] + dp[l][r - 1] - dp[l + 1][r - 1] + val;
        }
    }
    cout << dp[0][n - 1] << '\n';
}