Example

Input

crc
1


Output

crc
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string S;
int N;
ll k;

int dp1[2010][2010];
int f1(int l, int r){
	int& d = dp1[l][r];
	if(d != -1) return d;
	if(l > r) return d = 0;
	if(l == r) return d = 1;
	if(l + 1 == r && S[l] == S[r]) return d = 2;

	d = 1e9;
	d = min(d, f1(l + 1, r) + 2);
	d = min(d, f1(l, r - 1) + 2);
	if(S[l] == S[r]) d = min(d, f1(l + 1, r - 1) + 2);
	return d;
}

ll dp2[2010][2010];
ll f2(int l, int r, int rem){
	ll& d = dp2[l][r];
	if(rem < f1(l, r)) return 0;
	if(d != -1) return d;
	if(l >= r) return d = 1;
	if(l + 1 == r && S[l] == S[r]) return d = 1;

	d = 0;
	for(char i = 'a'; i <= 'z'; i++){
		int nl = l, nr = r;
		if(S[l] == i) nl++;
		if(S[r] == i) nr--;
		d += f2(nl, nr, rem - 2);
		d = min(d, k + 1);
	}
	return d;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	while(cin >> S >> k){
		N = S.size();
		memset(dp1, -1, sizeof dp1);
		memset(dp2, -1, sizeof dp2);
		int minlen = f1(0, N - 1);

		if(minlen == 1){
			if(k == 1) cout << S << endl;
			else cout << "NONE" << endl;
			continue;
		}
		string ans;
		int l = 0, r = N - 1;
		bool ok = true;
		for(int i = 0; i < minlen / 2; i++){
			char nxt = 0;
			int L = 0, R = 0;
			ll sum = 0;
			for(char c = 'a'; c <= 'z'; c++){
				int nl = l, nr = r;
				if(S[l] == c) nl++;
				if(S[r] == c) nr--;
				ll res = f2(nl, nr, minlen - 2 * (i + 1));
				if(sum + res < k){
					sum += res;
				}
				else{
					nxt = c;
					L = nl, R = nr;
					break;
				}
			}
			if(nxt){
				k -= sum;
				ans += nxt;
				l = L, r = R;
			}
			else{
				ok = false;
				break;
			}
		}

		if(!ok){
			cout << "NONE" << endl;
		}
		else{
			string rev = ans;
			reverse(rev.begin(), rev.end());
			if(minlen % 2){
				ans = ans + S[l] + rev;
			}
			else{
				ans += rev;
			}
			cout << ans << endl;
		}
	}
}