Example

Input

crc
1


Output

crc
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
typedef long long LL;
const int N=2005;
struct sl{
	LL v,num;
	sl(LL v_=0,LL num_=0){v=v_;num=num_;}
}f[N][N];
LL ans,n,m,z,x,y,len;
string s,c;
sl DP(int l,int r){
	if (l>=r) return f[l][r]=sl(0,1);
	if (f[l][r].num!=0) return f[l][r];
	if (s[l-1]==s[r-1]){
		f[l][r]=DP(l+1,r-1); return f[l][r];
	}
	sl t1,t2;
	t1=DP(l,r-1);t2=DP(l+1,r);
	++t1.v;++t2.v;
	if (t1.v==t2.v){
		f[l][r].v=t1.v;
		if (t1.num+t2.num<=n) f[l][r].num=t1.num+t2.num;
		else f[l][r].num=n+1;
	}
	else if (t1.v<t2.v) f[l][r]=t1;
	else f[l][r]=t2;
	return f[l][r];
}
void getans(int l,int r,int x,int y){
	if (l>r) return;
	if (l==r) {
		c[x]=s[l-1];return;
	}
	if (s[l-1]==s[r-1]) {
		c[x]=s[l-1];c[y]=s[r-1];
		getans(l+1,r-1,x+1,y-1);
	}
	else if (f[l][r-1].v==f[l+1][r].v){
		if (s[l-1]<s[r-1] && n<=f[l+1][r].num) {
			c[x]=c[y]=s[l-1];
			getans(l+1,r,x+1,y-1);
		}
		else if (s[l-1]<s[r-1] && n>f[l+1][r].num){
			c[x]=c[y]=s[r-1];
			n-=f[l+1][r].num;
			getans(l,r-1,x+1,y-1);
		}
		else if (s[l-1]>s[r-1] && n<=f[l][r-1].num){
			c[x]=c[y]=s[r-1];
			getans(l,r-1,x+1,y-1);
		}
		else if (s[l-1]>s[r-1] && n>f[l][r-1].num){
			c[x]=c[y]=s[l-1];
			n-=f[l][r-1].num;
			getans(l+1,r,x+1,y-1);
		}
	}
	else if (f[l][r-1].v<f[l+1][r].v){
		c[x]=c[y]=s[r-1];
		getans(l,r-1,x+1,y-1);
	}
	else {
		c[x]=c[y]=s[l-1];
		getans(l+1,r,x+1,y-1);
	}
}
int main(){
	//freopen("G.in","r",stdin);freopen("G.out","w",stdout);
	cin>>s;
	cin>>n;
	len=s.length();
	DP(1,len);
	ans=f[1][len].v+len;
	c.resize(ans);
	if (f[1][len].num<n) cout<<"NONE"<<endl;
	else{
		getans(1,len,0,ans-1);
		cout<<c<<endl;
	}
}