Example

Input

crc
1


Output

crc
#include<bits/stdc++.h>
#define ms(x,y) memset(x,y,sizeof(x))
#define ll long long 
#define pb push_back
using namespace std;

char s[2005];
ll f[2005][2005];
int g[2005][2005];
ll k;


int main(){

	scanf("%s",s+1);
	int len=strlen(s+1);
	cin>>k;
	for(int i=1;i<=len;i++){
		g[i][i]=0;
		g[i][i-1]=0;
		f[i][i]=1;
		f[i][i-1]=1;
	}
	for(int l=2;l<=len;l++)
		for(int u=1;u<=len;u++){
			int v=u+l-1;
			if(v>len)continue;
			if(s[u]==s[v]){
				g[u][v]=g[u+1][v-1];
				f[u][v]=f[u+1][v-1];
			}
			else{
				if(g[u+1][v]>g[u][v-1]){
					f[u][v]=f[u][v-1];
					g[u][v]=g[u][v-1]+1;
				}
				else if(g[u+1][v]<g[u][v-1]){
					f[u][v]=f[u+1][v];
					g[u][v]=g[u+1][v]+1;
				}
				else{
					g[u][v]=g[u+1][v]+1;
					f[u][v]=min(k,f[u+1][v]+f[u][v-1]);
				}
			}
		}

	if(k>f[1][len]){
		cout<<"NONE"<<endl;
		return 0;
	}
	vector<char>ans;
	ans.clear();
	int l=1,r=len;
	while(l<r){
		if(s[l]==s[r]){
			ans.pb(s[l]);
			l++;r--;
			continue;
		}
		if(g[l+1][r] < g[l][r-1]){
			ans.pb(s[l]);
			l++;			
		}
		else if(g[l+1][r] == g[l][r-1]){
			if(s[l]<s[r]){
				if(f[l+1][r]>=k){
					ans.pb(s[l]);
					l++;
				}
				else{
					k-=f[l+1][r];
					ans.pb(s[r]);
					r--;
				}
			}
			else{
				if(f[l][r-1]>=k){
					ans.pb(s[r]);
					r--;
				}
				else{
					k-=f[l][r-1];
					ans.pb(s[l]);
					l++;
				}
			}
		}else{
			ans.pb(s[r]);
			r--;
		}
	}



	/*		
		if(g[l+1][r] == g[l][r-1]){
			ll tmp=min(f[l+1][r],f[l][r-1]);
			if((s[l]>s[r]) ^ (k<=tmp)){
				ans.pb(s[l]);
				l++; 
			}
			else{
				ans.pb(s[r]);
				r--;
			}
			if(k>tmp)k-=tmp;
		}
		else{
			if(g[l+1][r]<g[l][r-1]){
				ans.pb(s[l]);
				l++;
			}
			else{
				ans.pb(s[r]);
				r--;
			}
		}*/
	int siz=ans.size();
	for(int i=0;i<siz;i++)
		printf("%c",ans[i]);
	if(l==r)
		printf("%c",s[l]);
	for(int i=siz-1;i>=0;i--)
		printf("%c",ans[i]);
	printf("\n");
	return 0;
}