Example

Input

crc
1


Output

crc
#include<cstdio>
#include<cstring>
#include<iostream>
#define N 2010
#define LL long long
#define inf 0x7fffffff/2
using namespace std;

int len, f[N][N], fl, fr;
LL k, g[N][N];
char s[N], data[N << 1];
int min(int a, int b){return (a < b)? a : b;}

void DP(int l, int r)
{
	if (l >= r){f[l][r] = 0; g[l][r] = 1; return;}
	if (f[l][r] != -1) return;
	if (s[l] == s[r])
	{
		DP(l + 1, r - 1);
		f[l][r] = f[l + 1][r - 1];
		g[l][r] = g[l + 1][r - 1];
		return;
	}
	f[l][r] = inf; g[l][r] = 0;
	DP(l + 1, r); f[l][r] = min(f[l][r], f[l + 1][r] + 1);
	DP(l, r - 1); f[l][r] = min(f[l][r], f[l][r - 1] + 1);
	if (f[l][r] == f[l + 1][r] + 1) g[l][r] += g[l + 1][r];
	if (f[l][r] == f[l][r - 1] + 1) g[l][r] += g[l][r - 1];
	if (g[l][r] > k) g[l][r] = k + 1;
}

void Find(int l, int r, LL k)
{
	if (l > r) return;
	if (l == r) {data[fl] = s[l]; return;}
	if (s[l] == s[r])
	{
		data[fl++] = s[l];
		data[fr--] = s[r];
		Find(l + 1, r - 1, k);
		return;
	}
	if (f[l][r] == f[l + 1][r] + 1 && f[l][r] != f[l][r - 1] + 1)
	{
		data[fl++] = data[fr--] = s[l];
		Find(l + 1, r, k);
		return;
	}
	else if (f[l][r] == f[l][r - 1] + 1 && f[l][r] != f[l + 1][r] + 1)
	{
		data[fl++] = data[fr--] = s[r];
		Find(l, r - 1, k);
		return;
	}
	if (s[l] < s[r])
	{
		if (k <= g[l + 1][r])
		{
			data[fl++] = data[fr--] = s[l];
			Find(l + 1, r, k);
			return;
		}
		else
		{
			data[fl++] = data[fr--] = s[r];
			Find(l, r - 1, k - g[l + 1][r]);
			return;
		}
	}
	else
	{
		if (k <= g[l][r - 1])
		{
			data[fl++] = data[fr--] = s[r];
			Find(l, r - 1, k);
			return;
		}
		else 
		{
			data[fl++] = data[fr--] = s[l];
			Find(l + 1, r, k - g[l][r - 1]);
			return;
		}
	}
}

int main()
{
	scanf("%s", s); cin >> k;
	len = strlen(s);
	memset(f, -1, sizeof f);
	DP(0, len - 1);
	if (k > g[0][len - 1])
	{
		printf("NONE\n");
		return 0;
	}
	fl = 0; fr = f[0][len - 1] + len - 1;
	Find(0, len - 1, k);
	for (int i = 0; i < f[0][len - 1] + len; i++) printf("%c", data[i]);printf("\n");
	return 0;
} 