Example

Input

crc
1


Output

crc
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 1e9;

ll maxK = 1e18;

bool m[2000][2001] = {0};
int len[2000][2001];
ll pattern[2000][2001] = {0};
string str;
int N;
bool inRange(int l, int r) {
	return r >= l && 0 <= l && l < N && 0 <= r && r <= N;
}
ll dp(int l, int r) {
	ll res = INF;
	if (m[l][r]) return len[l][r];
	if (r-l <= 1) {
		res = 0;
		pattern[l][r] = 1;
	}
	else if (inRange(l+1, r-1) && str[l] == str[r-1]) {
		res = dp(l+1, r-1);
		pattern[l][r] = pattern[l+1][r-1];
	}
	else {
		if ( inRange(l+1, r) ) {
			res = dp(l+1, r)+1;
			pattern[l][r] = pattern[l+1][r];
		}
		if ( inRange(l, r-1) ) {
			if (dp(l, r-1)+1 <= res) {
				if (dp(l, r-1)+1 < res) {
					pattern[l][r] = 0;
				}
				res = dp(l, r-1)+1;
				pattern[l][r] = min(maxK+1, pattern[l][r]+pattern[l][r-1]);
			}
		}
	}
	return m[l][r] = true, len[l][r] = res;
}
string solve(ll K) {
	for (int l = 0; l < N; ++l) {
		for (int r = l; r <= N; ++r) {
			dp(l, r);
		}
	}
/*
	for (int w = 0; w < N; ++w) {
		for (int l = 0, r = l+w; r <= N; ++l, ++r) {
//			cout << l << " " << r << endl;
			if (l-1 >= 0 && r < N && str[l-1] == str[r]) {
				if (len[l][r] < len[l-1][r+1]) {
					len[l-1][r+1] = len[l][r];
					pattern[l-1][r+1] = 0;
				}
				if (len[l][r] == len[l-1][r+1]) {
					pattern[l-1][r+1] += pattern[l][r];
				}
			}
			else {
				if (l-1 >= 0) {
					if (len[l][r]+1 < len[l-1][r]) {
						len[l-1][r] = len[l][r]+1;
						pattern[l-1][r] = 0;
					}
					if (len[l][r]+1 == len[l-1][r]) {
						pattern[l-1][r] += pattern[l][r];
					}
				}
				if (r+1 <= N) {
					if (len[l][r]+1 < len[l][r+1]) {
						len[l][r+1] = len[l][r]+1;
						pattern[l][r+1] = 0;
					}
					if (len[l][r]+1 == len[l][r+1]) {
						pattern[l][r+1] += pattern[l][r];
					}
				}
			}
		}
	}
*/
	for (int i = 0; i <= N; ++i) {
		for (int j = i; j <= N; ++j) {
//			cout << i << " " << j << " " << len[i][j] << " " << pattern[i][j] << endl;
		}
	}
//	cout << ":" << len[0][N] << " " << pattern[0][N] << endl;
	if (pattern[0][N] < K) {
		return "NONE";
	}
	else {
		string ans = "", mid = "";
		int l = 0, r = N;
		while (r-l > 0) {
//			cout << l << " " << r << " " << K << " " << pattern[l][r] << " " << ans << endl;
			if (r-l == 1) {
				mid += str[l];
				--r;
			}
			else if (str[l] == str[r-1]) {
//				assert(pattern[l][r] == pattern[l+1][r-1]);
				ans += str[l];
				++l, --r;
			}
			else {
				if (len[l+1][r] == len[l][r-1]) {
//					assert(pattern[l+1][r] + pattern[l][r-1] == pattern[l][r]);
					if (str[l] < str[r-1]) {
						if (K <= pattern[l+1][r]) {
							ans += str[l];
							++l;
						}
						else {
							K -= pattern[l+1][r];
							ans += str[r-1];
							--r;
						}
					}
					else {
						if (K <= pattern[l][r-1]) {
							ans += str[r-1];
							--r;
						}
						else {
							K -= pattern[l][r-1];
							ans += str[l];
							++l;
						}
					}
				}
				else if (len[l+1][r] < len[l][r-1]) {
//					assert(pattern[l][r] == pattern[l+1][r]);
					ans += str[l];
					++l;
				}
				else {
//					assert(pattern[l][r] == pattern[l][r-1]);
					ans += str[r-1];
					--r;
				}
			}
		}
//		assert(K == 1);
		string rans = ans; reverse(rans.begin(), rans.end());
		ans = ans + mid + rans;
		return ans;
	}
}
int main() {
	cin >> str;
	N = str.size();
	ll K; cin >> K;
	fill(len[0], len[2000], INF);
	cout << solve(K) << endl;
/*
	set<string> s;
	for (int i = 0; i < 8; ++i) {
		string ans = solve(i+1);
		s.insert(ans);
		cout << ans << endl;
	}
	cout << s.size() << endl;
*/
}