Example

Input

crc
1


Output

crc
#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

long long dp[2009][2009], dp2[2009][2009], LP[2009], k, n, INF = 1200000000000000000LL; string S;

int main() {
	cin >> S >> k; n = S.size();
	for (int i = 1; i <= n; i++) LP[i] = S[i - 1] - 'a';
	for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) dp[i][j] = 10000; }
	for (int i = 1; i <= n; i++) { dp[i][i - 1] = 0; dp2[i][i - 1] = 1; dp[i][i] = 1; dp2[i][i] = 1; }
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n - i; j++) {
			int L = j, R = i + j;
			if (LP[L] == LP[R]) { dp[L][R] = dp[L + 1][R - 1] + 2; dp2[L][R] = dp2[L + 1][R - 1]; continue; }

			if (dp[L][R] > dp[L + 1][R] + 2) { dp[L][R] = dp[L + 1][R] + 2; dp2[L][R] = dp2[L + 1][R]; }
			else if (dp[L][R] == dp[L + 1][R] + 2) { dp2[L][R] += dp2[L + 1][R]; }

			if (dp[L][R] > dp[L][R - 1] + 2) { dp[L][R] = dp[L][R - 1] + 2; dp2[L][R] = dp2[L][R - 1]; }
			else if (dp[L][R] == dp[L][R - 1] + 2) { dp2[L][R] += dp2[L][R - 1]; }

			if (dp2[L][R] >= INF) dp2[L][R] = INF;
		}
	}
	if (dp2[1][n] < k) { cout << "NONE" << endl; return 0; }
	string V = ""; int LL = 1, RR = n;
	while (LL < RR) {
		vector<tuple<int, int, int>>vec;
		if (LP[LL] == LP[RR] && dp[LL + 1][RR - 1] + 2 == dp[LL][RR]) vec.push_back(make_tuple(LP[LL], 1, 1));
		else {
			if (dp[LL][RR - 1] + 2 == dp[LL][RR]) vec.push_back(make_tuple(LP[RR], 0, 1));
			if (dp[LL + 1][RR] + 2 == dp[LL][RR]) vec.push_back(make_tuple(LP[LL], 1, 0));
		}
		sort(vec.begin(), vec.end());

		for (int i = 0; i < vec.size(); i++) {
			int L1 = LL + get<1>(vec[i]), R1 = RR - get<2>(vec[i]);
			if (k <= dp2[L1][R1]) { V += ('a' + get<0>(vec[i])); LL = L1; RR = R1; break; }
			k -= dp2[L1][R1];
		}
	}
	string VV = V; reverse(VV.begin(), VV.end());
	if (dp[1][n] % 2 == 0) V += VV;
	else V = V + S[LL - 1] + VV;
	cout << V << endl;
	return 0;
}
