Example

Input

crc
1


Output

crc
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;


ll N,K;
string S;
string ans="";
bool flag=false;



bool visited[2005][2005];
P mem[2005][2005];

P rec(int l,int r){
  if(visited[l][r])return mem[l][r];
  visited[l][r]=true;

  if(l==r){
    return mem[l][r]=P(1,1);
  }

  if(l-1==r){
    return mem[l][r]=P(0,1);
  }
  
  if(S[l]==S[r]){
    P tmp=rec(l+1,r-1);
    tmp.first+=2;
    return mem[l][r]=tmp;
  }

  P pa=rec(l+1,r);
  P pb=rec(l,r-1);
  if(pa.first<pb.first){
    pa.first+=2;
    return mem[l][r]=pa;
  }else if(pa.first>pb.first){
    pb.first+=2;
    return mem[l][r]=pb;
  }else if(pa.first==pb.first){
    pa.first+=2;
    pa.second+=pb.second;
    if(pa.second>K)pa.second=K+1;
    return mem[l][r]=pa;
  }
}


void dfs(int l,int r,ll k){
  if(l==r){
    if(k!=1)flag=true;

    ans+=S[l];
    return;
  }

  if(l-1==r){
    if(k!=1)flag=true;

    return;
  }

  if(S[l]==S[r]){
    ans+=S[l];
    dfs(l+1,r-1,k);
    return;
  }

  P lp=mem[l+1][r];
  P rp=mem[l][r-1];

  if(lp.first < rp.first){
    ans+=S[l];
    dfs(l+1,r,k);
    return;
  }

  if(lp.first > rp.first){
    ans+=S[r];
    dfs(l,r-1,k);
    return;
  }

  if(S[l]<S[r]){
    if(k<=lp.second){
      ans+=S[l];
      dfs(l+1,r,k);
      return;
    }
    k-=lp.second;
    if(k<=rp.second){
      ans+=S[r];
      dfs(l,r-1,k);
      return;
    }
    flag=true;
    return;
  }else if(S[l]>S[r]){
    if(k<=rp.second){
      ans+=S[r];
      dfs(l,r-1,k);
      return;
    }
    k-=rp.second;
    if(k<=lp.second){
      ans+=S[l];
      dfs(l+1,r,k);
      return;
    }
    flag=true;
    return;
  }

}

int main(){
  cin>>S>>K;
  N=S.size();
  P p=rec(0,N-1);
  dfs(0,N-1,K);
  if(flag){
    cout<<"NONE"<<endl;
  }else{
    int size=ans.size();
    if(p.first%2==1){
      for(int i=0;i+1<size;i++)cout<<ans[i];
      for(int i=size-1;i>=0;i--)cout<<ans[i];
      cout<<endl;
    }else{
      for(int i=0;i<size;i++)cout<<ans[i];
      for(int i=size-1;i>=0;i--)cout<<ans[i];
      cout<<endl;
    }

  }
  return 0;
}