Example

Input

crc
1


Output

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

typedef long long ll;
typedef pair<int,ll> P;
string S;
ll K;

ll pl( ll a, ll b ){
  if( a > K ) return K+1;
  if( b > K ) return K+1;
  if( a+b > K ) return K+1;
  return a+b;
}

P dp[2222][2222];

void update( P &a, P b, int t=0 ){
  b.first+=t;
  a = b;
}
void update( P &a, P b, P c ){
  b.first+=2; c.first+=2;
  if( b.first == c.first ){
    ll x = pl( b.second, c.second );
    b.second = x;
    update( a, b );
  } else if( b.first < c.first )
    update( a, b );
  else
    update( a, c );
}

P solve( int l, int r ){
  P &ret = dp[l][r];
  if( ret.second != -1 ) return ret;  
  if( l == r ) return ret = P(1,1);
  if( l > r ) return ret = P(0,1);
  if( S[l] == S[r] ) update( ret, solve(l+1,r-1), 2 );
  else update( ret, solve(l+1,r), solve(l,r-1) );
  return ret;
}

string res;

void solve( int l, int r, ll k ){
  //  cout << l << " " << r<< " " << k << " " << dp[l][r].second << endl;
  //cout << res << endl;
  if( l == r ){    
    string rv = res; reverse( rv.begin(), rv.end() );
    res += S[l]; res += rv;
  } else if( l > r ) {
    string rv = res; reverse( rv.begin(), rv.end() );
    res += rv;
  } else {
    if( S[l] == S[r] ) {
      res += S[l]; solve( l+1, r-1, k );
    } else if( dp[l+1][r].first > dp[l][r-1].first ) {//+r
      res += S[r];
      solve( l, r-1, k );
    } else if( dp[l+1][r].first < dp[l][r-1].first ) {//+l
      res += S[l];
      solve( l+1,r, k );
    } else if( S[l] > S[r] ) {
      ll nk = pl( k, dp[l][r-1].second );
      if( nk > K ) {//+r
        res += S[r]; solve( l, r-1, k );
      } else {//+l
        res += S[l]; solve( l+1, r, nk );
      }
    } else {
      ll nk = pl( k, dp[l+1][r].second );
      if( nk > K ) {//+l
        res += S[l]; solve( l+1, r, k );
      } else {//+r
        res += S[r]; solve( l, r-1, nk );
      }
    }
  }
}

int main(){
  cin >> S;
  cin >> K;
  fill( dp[0],dp[2001],P((1<<30),-1) );
  if( solve( 0, S.size()-1 ).second < K ) {
    cout << "NONE" << endl; return 0;
  }
  solve( 0, S.size()-1, 1 );
  cout << res << endl;
}