#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long LL;
const int N = 2005;

LL K;
char str[N];
int f[N][N];
LL g[N][N];

void getg(int l, int r) {
    if (g[l][r] != -1) return ;
    if (r - l + 1 + f[l][r - l + 1] == 0) {
        g[l][r] = 1;
        return ;
    }
    if (l == r) {
        g[l][r] = 1;
        return ;
    }
    g[l][r] = 0;
    for (char pos = 'a'; pos <= 'z'; ++pos) {
        int l1 = l, r1 = r;
        if (str[l1] == pos) ++l1;
        if (str[r1] == pos) --r1;
        if (f[l1][r1 - l1 + 1] + r1 - l1 + 1 + 2 == f[l][r - l + 1] + r - l + 1) {
            getg(l1, r1);
            g[l][r] += g[l1][r1];
            if (g[l][r] > K) g[l][r] = K + 1;
        }
    }
}

char str1[100000];

void solve(int l, int r, int L, int R) {
    if (L > R) return ;
    if (l == r) {
        str1[L] = str[l];
        return ;
    }
    for (char pos = 'a'; pos <= 'z'; ++pos) {
        int l1 = l, r1 = r;
        if (str[l1] == pos) ++l1;
        if (str[r1] == pos) --r1;
        if (f[l1][r1 - l1 + 1] + r1 - l1 + 1 + 2 == f[l][r - l + 1] + r - l + 1) {
            //if (l == 1 && r == 5)
            //    cout << g[l1][r1] << endl;
            if (g[l1][r1] < K) {
                K -= g[l1][r1];
                continue;
            }
            // cout << 1 << endl;
            str1[L] = str1[R] = pos;
            solve(l1, r1, L + 1, R - 1);
            return ;
        }
    }
}

int main() {
    gets(str + 1);
    int n = strlen(str + 1);
    scanf("%lld", &K);
    for (int len = 2; len <= n; ++len)
        for (int s = 1; s + len - 1 <= n; ++s) {
            f[s][len] = 1 << 30;
            f[s][len] = min(f[s][len], f[s][len - 1] + 1);
            f[s][len] = min(f[s][len], f[s + 1][len - 1] + 1);
            if (str[s] == str[s + len - 1])
                f[s][len] = min(f[s][len], f[s + 1][len - 2]);
        }
    memset(g, -1, sizeof(g));
    getg(1, n);
    if (g[1][n] < K) {
        puts("NONE");
        return 0;
    }
    solve(1, n, 1, f[1][n] + n);
    puts(str1 + 1);
}
/*
thdstodxtksrnfacdsohnlfuivqvqsozdstwaszmkboehgcerwxawuojpfuvlxxdfkezprodnettawsyqazekcftgqbrrtkzngaxzlnphynkmsdsdleqaxnhehwzgzwtldwaacfczqkfpvxnalnnhfzbagzhqhstcymdeijlbkbbubdnptolrmemfxlmmzhfpshykxvzbjmcnsusllpyqghzhdvljdxrrebeef
11469362357953500
 */
### Prompt

Your task is to create a cpp solution to the following problem:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cctype>
using namespace std;
typedef long long LL;
const int N = 2005;

LL K;
char str[N];
int f[N][N];
LL g[N][N];

void getg(int l, int r) {
    if (g[l][r] != -1) return ;
    if (r - l + 1 + f[l][r - l + 1] == 0) {
        g[l][r] = 1;
        return ;
    }
    if (l == r) {
        g[l][r] = 1;
        return ;
    }
    g[l][r] = 0;
    for (char pos = 'a'; pos <= 'z'; ++pos) {
        int l1 = l, r1 = r;
        if (str[l1] == pos) ++l1;
        if (str[r1] == pos) --r1;
        if (f[l1][r1 - l1 + 1] + r1 - l1 + 1 + 2 == f[l][r - l + 1] + r - l + 1) {
            getg(l1, r1);
            g[l][r] += g[l1][r1];
            if (g[l][r] > K) g[l][r] = K + 1;
        }
    }
}

char str1[100000];

void solve(int l, int r, int L, int R) {
    if (L > R) return ;
    if (l == r) {
        str1[L] = str[l];
        return ;
    }
    for (char pos = 'a'; pos <= 'z'; ++pos) {
        int l1 = l, r1 = r;
        if (str[l1] == pos) ++l1;
        if (str[r1] == pos) --r1;
        if (f[l1][r1 - l1 + 1] + r1 - l1 + 1 + 2 == f[l][r - l + 1] + r - l + 1) {
            //if (l == 1 && r == 5)
            //    cout << g[l1][r1] << endl;
            if (g[l1][r1] < K) {
                K -= g[l1][r1];
                continue;
            }
            // cout << 1 << endl;
            str1[L] = str1[R] = pos;
            solve(l1, r1, L + 1, R - 1);
            return ;
        }
    }
}

int main() {
    gets(str + 1);
    int n = strlen(str + 1);
    scanf("%lld", &K);
    for (int len = 2; len <= n; ++len)
        for (int s = 1; s + len - 1 <= n; ++s) {
            f[s][len] = 1 << 30;
            f[s][len] = min(f[s][len], f[s][len - 1] + 1);
            f[s][len] = min(f[s][len], f[s + 1][len - 1] + 1);
            if (str[s] == str[s + len - 1])
                f[s][len] = min(f[s][len], f[s + 1][len - 2]);
        }
    memset(g, -1, sizeof(g));
    getg(1, n);
    if (g[1][n] < K) {
        puts("NONE");
        return 0;
    }
    solve(1, n, 1, f[1][n] + n);
    puts(str1 + 1);
}
/*
thdstodxtksrnfacdsohnlfuivqvqsozdstwaszmkboehgcerwxawuojpfuvlxxdfkezprodnettawsyqazekcftgqbrrtkzngaxzlnphynkmsdsdleqaxnhehwzgzwtldwaacfczqkfpvxnalnnhfzbagzhqhstcymdeijlbkbbubdnptolrmemfxlmmzhfpshykxvzbjmcnsusllpyqghzhdvljdxrrebeef
11469362357953500
 */
```