Example

Input

crc
1


Output

crc
#include <bits/stdc++.h>
#define INF 1LL<<60
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

string str;
ll k;
int n;

int dp[2001][2001];
ll cnt[2005][2005];
char ss[5001];

int func(int l,int r){
	if(dp[l][r]!=-1)return dp[l][r];
	if(l==r){
		cnt[l][r]=1;
		return 0;
	}
	if((l+1)==r){
		cnt[l][r]=1;
		return 1;
	}
	int ans=func(l+1,r)+2;
	ll val=cnt[l+1][r];
	int v2=func(l,r-1)+2;
	if(v2==ans)val+=cnt[l][r-1];
	else if(v2<ans)val=cnt[l][r-1];
	ans=min(ans,v2);
	if(str[l]==str[r-1]){
		v2=func(l+1,r-1)+2;
		val=cnt[l+1][r-1];
		ans=min(v2,ans);
	}
	cnt[l][r]=min(val,1LL<<60);
	return (dp[l][r]=ans);
}

void solve(int l,int r,int c,ll rest){
	if(l==r)return;
	if((l+1)==r){
		ss[c]=str[l];
		ss[n-c-1]=str[l];
		return;
	}
	if(str[l]==str[r-1]){
		ss[c]=str[l];
		ss[n-c-1]=str[l];
		c++;
		solve(l+1,r-1,c,rest);
	}else{
		if(dp[l+1][r]<dp[l][r-1]){
			ss[c]=str[l];
			ss[n-c-1]=str[l];
			c++;
			solve(l+1,r,c,rest);
		}else if(dp[l+1][r]>dp[l][r-1]){
			ss[c]=str[r-1];
			ss[n-c-1]=str[r-1];
			c++;
			solve(l,r-1,c,rest);
		}else{
			if(str[l]<str[r-1]){
				if(cnt[l+1][r]>rest){
					ss[c]=str[l];
					ss[n-c-1]=str[l];
					c++;
					solve(l+1,r,c,rest);
				}else{
					ss[c]=str[r-1];
					ss[n-c-1]=str[r-1];
					c++;
					rest-=cnt[l+1][r];
					solve(l,r-1,c,rest);
				}
			}else{
				if(cnt[l][r-1]>rest){
					ss[c]=str[r-1];
					ss[n-c-1]=str[r-1];
					c++;
					solve(l,r-1,c,rest);
				}else{
					ss[c]=str[l];
					ss[n-c-1]=str[l];
					c++;
					rest-=cnt[l][r-1];
					solve(l+1,r,c,rest);
				}
			}
		}
	}
}

int main(void){
	cin >> str;
	n=str.size();
	scanf("%lld",&k);
	memset(dp,-1,sizeof(dp));
	int pn=n;
	n=func(0,n);
	k--;
	if(cnt[0][pn]<=k)printf("NONE\n");
	else{
		solve(0,pn,0,k);
		for(int i=0;i<n;i++){
			printf("%c",ss[i]);
		}
		printf("\n");
	}
	return 0;
}
