Example

Input

crc
1


Output

crc
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, ll>;

using namespace std;

string S;
ll k;
int N;
P memo[2002][2002];

P dfs(int l, int r){
	if(l == r){
		return P(1, 1);
	}else if(r < l){
		return P(0, 1);
	}
	if(memo[l][r].first != -1) return memo[l][r];
	P ret;
	if(S[l] == S[r]){
		P res = dfs(l + 1, r - 1);
		ret = P(res.first + 2, res.second);
	}else{
		P resl = dfs(l + 1, r);
		P resr = dfs(l, r - 1);
		if(resl.first == resr.first){
			ret = P(resl.first + 2, min(k + 1, resl.second + resr.second));
		}else{
			ret = min(resl, resr);
			ret.first += 2;
		}
	}
	memo[l][r] = ret;
	return ret;
}

string ans;
int ansl, ansr;
ll cnt;

void build_ans(int l, int r, ll cur){
	if(l == r){
		ans[ansl] = S[l];
		return;
	}else if(r < l){
		return;
	}
	if(S[l] == S[r]){
		ans[ansl++] = S[l];
		ans[ansr--] = S[l];
		build_ans(l + 1, r - 1, cur);
	}else{
		P resl = dfs(l + 1, r);
		P resr = dfs(l, r - 1);

		if(resl.first == resr.first){
			if(S[l] < S[r]){
				if(k <= cur + resl.second){
					ans[ansl++] = S[l];
					ans[ansr--] = S[l];
					build_ans(l + 1, r, cur);
				}else{
					ans[ansl++] = S[r];
					ans[ansr--] = S[r];
					build_ans(l, r - 1, cur + resl.second);
				}
			}else{
				if(k <= cur + resr.second){
					ans[ansl++] = S[r];
					ans[ansr--] = S[r];
					build_ans(l, r - 1, cur);
				}else{
					ans[ansl++] = S[l];
					ans[ansr--] = S[l];
					build_ans(l + 1, r, cur + resr.second);
				}
			}
		}else if(resl.first < resr.first){
			ans[ansl++] = S[l];
			ans[ansr--] = S[l];
			build_ans(l + 1, r, cur);
		}else{
			ans[ansl++] = S[r];
			ans[ansr--] = S[r];
			build_ans(l, r - 1, cur);
		}
	}
}

int main() {
	cin >> S >> k;
	N = S.size();

	for(int i=0;i<=N;i++){
		for(int j=0;j<=N;j++){
			memo[i][j] = P(-1, -1);
		}
	}
	P res = dfs(0, N - 1);
	if(res.second < k){
		cout << "NONE" << endl;
	}else{
		ans.assign(res.first, '.');
		ansl = 0;
		ansr = res.first - 1;
		build_ans(0, N - 1, 0);
		cout << ans << endl;
	}

	return 0;
}