Example

Input

crc
1


Output

crc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

string s;
ll k;
ll n;
ll dp[2001][2001];
ll cnt[2001][2001];

ll dfs(ll l,ll r){
  if(l>r){
    cnt[l][r]=1;
    return 0;
  }
  if(dp[l][r]!=-1)return dp[l][r];
  ll res;
  if(s[l]==s[r]){
    res=dfs(l+1,r-1)+(l==r?1:2);
    cnt[l][r]=cnt[l+1][r-1];
  }else{
    ll resl=dfs(l+1,r)+2;
    ll resr=dfs(l,r-1)+2;
    if(resl==resr){
      res=resl;
      cnt[l][r]=cnt[l+1][r]+cnt[l][r-1];
    }else if(resl<resr){
      res=resl;
      cnt[l][r]=cnt[l+1][r];
    }else{
      res=resr;
      cnt[l][r]=cnt[l][r-1];
    }
  }
  if(cnt[l][r]>1e18)cnt[l][r]=1e18+1;
  return dp[l][r]=res;
}

string dfs2(ll l,ll r,ll crtk){
  if(l>r)return "";
  if(l==r)return s.substr(l,1);
  string res;
  if(s[l]==s[r]){
    res+=s[l];
    res+=dfs2(l+1,r-1,crtk);
    res+=s[r];
  }else{
    if(dp[l+1][r]==dp[l][r-1]){
      if(s[l]<s[r]){
        if(crtk<=cnt[l+1][r]){
          res+=s[l];
          res+=dfs2(l+1,r,crtk);
          res+=s[l];
        }else{
          crtk-=cnt[l+1][r];
          res+=s[r];
          res+=dfs2(l,r-1,crtk);
          res+=s[r];
        }
      }else{
        if(crtk<=cnt[l][r-1]){
          res+=s[r];
          res+=dfs2(l,r-1,crtk);
          res+=s[r];
        }else{
          crtk-=cnt[l][r-1];
          res+=s[l];
          res+=dfs2(l+1,r,crtk);
          res+=s[l];
        }
      }
    }else if(dp[l+1][r]<dp[l][r-1]){
      res+=s[l];
      res+=dfs2(l+1,r,crtk);
      res+=s[l];
    }else{
      res+=s[r];
      res+=dfs2(l,r-1,crtk);
      res+=s[r];
    }
  }
  return res;
}

int main(){
  cin>>s>>k;
  n=s.size();
  memset(dp,-1,sizeof(dp));
  dfs(0,n-1);
  if(cnt[0][n-1]<k){
    cout<<"NONE"<<endl;
    return 0;
  }
  string res=dfs2(0,n-1,k);
  cout<<res<<endl;
  return 0;
}

