Example

Input

crc
1


Output

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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)

typedef long long ll;

char s[2521];
int n;
ll k;

ll dp[2521][2521];
int len[2521][2521];

const ll INF = 2000000000000000000ll;

int main(){
  scanf("%s",s);
  n = strlen(s);
  scanf("%lld",&k);
  // ll maxval = 0;
  FOR(l,0,n+1)REP(i,n-l+1){
    int j = i+l;
    if(j-i<=1){
      len[i][j] = j-i;
      dp[i][j] = 1;
      continue;
    }
    if(s[i]==s[j-1]){
      len[i][j] = len[i+1][j-1] + 2;
      dp[i][j] = dp[i+1][j-1];
      continue;
    }
    int minlen = min(len[i+1][j], len[i][j-1]);
    len[i][j] = minlen + 2;
    if(minlen == len[i+1][j]){
      dp[i][j] += dp[i+1][j];
    }
    if(minlen == len[i][j-1]){
      dp[i][j] += dp[i][j-1];
    }
    dp[i][j] = min(dp[i][j], INF);
    // maxval = max(maxval, dp[i][j]);
  }
  // cout << maxval << endl;
  if(dp[0][n] < k){
    puts("NONE");
    return 0;
  }
  int i = 0, j = n;
  string head = "", tail = "";
  while(j-i>1){
    if(s[i]==s[j-1]){
      head += s[i];
      tail += s[j-1];
      i++; j--; continue;
    }
    if(len[i+1][j] < len[i][j-1]){
      head += s[i];
      tail += s[i];
      i++; continue;
    }else if(len[i+1][j] > len[i][j-1]){
      head += s[j-1];
      tail += s[j-1];
      j--; continue;
    }else{
      if(s[i] < s[j-1]){
        if(k <= dp[i+1][j]){
          head += s[i];
          tail += s[i];
          i++; continue;
        }else{
          head += s[j-1];
          tail += s[j-1];
          k-=dp[i+1][j];
          j--; continue;
        }
      }else{
        if(k <= dp[i][j-1]){
          head += s[j-1];
          tail += s[j-1];
          j--; continue;
        }else{
          head += s[i];
          tail += s[i];
          k-=dp[i][j-1];
          i++; continue;
        }
      }
    }
  }
  string ans = head;
  reverse(tail.begin(), tail.end());
  FOR(x,i,j)ans += s[x];
  ans += tail;
  cout<<ans<<endl;
  return 0;
}