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

typedef long long ll;

const int N = 2e3 + 5;

struct A {
  int l;
  ll sum;
} dp[N][N];

char s[N];
char ans[2 * N];
int cn;
ll k;

int dfs(int l, int r) {
  if(dp[l][r].l != -1) return dp[l][r].l;
  if(l == r) {
    dp[l][r] = (A){1, 1}; return 1;
  }
  if(l > r) {
    dp[l][r] = (A){0, 1}; return 0;
  }
  if(s[l] == s[r]) {
    dp[l][r].l = dfs(l + 1, r - 1) + 2;
    dp[l][r].sum = dp[l+1][r-1].sum;
    return dp[l][r].l;
  }
  int la = dfs(l + 1, r);
  int ra = dfs(l, r - 1);
  dp[l][r].l = min(la, ra) + 2;
  if(la + 2 == dp[l][r].l) dp[l][r].sum += dp[l+1][r].sum;
  if(ra + 2 == dp[l][r].l) dp[l][r].sum += dp[l][r-1].sum;
  //cout << dp[l][r].sum << endl;
  if(dp[l][r].sum > k) dp[l][r].sum = k + 1;
  return dp[l][r].l;
}

void dfsn(int l, int r, int be) {
  if(l == r) {
    ans[be] = s[l]; return ;
  }
  if(l > r) return ;
  int len = dp[l][r].l;
  if(s[l] == s[r]) {
    ans[be] = ans[be+len-1] = s[l];
    dfsn(l+1, r-1, be+1); return ;
  }
  int la = dp[l+1][r].l;
  int lb = dp[l][r-1].l;
  if(la != dp[l][r].l-2) {
    ans[be] = ans[be+len-1] = s[r];
    //if(dp[l][r].l != lb+2) cout<<"error!"<<endl;
    //cout << be << " " << len << " " << s[r] << endl;
    dfsn(l, r-1, be+1); return ;
  } else
  if(lb != dp[l][r].l-2) {
    ans[be] = ans[be+len-1] = s[l];
    //cout << be << " " << len << " " << s[l] << endl;
    dfsn(l+1, r, be+1); return ;
  }
  //cout << dp[l+1][r].sum << " " << dp[l][r-1].sum << endl;
  if(s[l] < s[r]) {
    if(dp[l+1][r].sum >= k) {
      ans[be] = ans[be+len-1] = s[l];
      //cout << be << " " << len << " " << s[l] << endl;
      dfsn(l+1, r, be+1); return ;
    } else {
      ans[be] = ans[be+len-1] = s[r];
      k -= dp[l+1][r].sum;
      //cout << be << " " << len << " " << s[r] << endl;
      dfsn(l, r-1, be+1); return ;
    }
  } else if(s[l] > s[r]) {
    if(dp[l][r-1].sum >= k) {
      ans[be] = ans[be+len-1] = s[r];
      //cout << be << " " << len << " " << s[r] << endl;
      dfsn(l, r-1, be+1); return ;
    } else {
      ans[be] = ans[be+len-1] = s[l];
      k -= dp[l][r-1].sum;
      //cout << be << " " << len << " " << s[l] << endl;
      dfsn(l+1, r, be+1); return ;
    }
  }
}

int main() {
  //freopen("out", "w", stdout);
  scanf("%s%lld", s, &k);
  int len = strlen(s);
  for(int i = 0; i < len; ++ i)
    for(int j = 0; j < len; ++ j)
      dp[i][j].l = -1, dp[i][j].sum = 0;

  int m = dfs(0, len-1); cn = 0;
  //cout << dp[1][len-1].sum << endl;
  if(k > dp[0][len-1].sum) {
    puts("NONE"); return 0;
  }
  //cout << m << endl;
  dfsn(0, len-1, 0);
  ans[m] = '\n';
  printf("%s", ans);
  return 0;
}
/*
thdstodxtksrnfacdsohnlfuivqvqsozdstwaszmkboehgcerwxawuojpfuvlxxdfkezprodnettawsyqazekcftgqbrrtkzngaxzlnphynkmsdsdleqaxnhehwzgzwtldwaacfczqkfpvxnalnnhfzbagzhqhstcymdeijlbkbbubdnptolrmemfxlmmzhfpshykxvzbjmcnsusllpyqghzhdvljdxrrebeef
11469362357953500
*/

### Prompt

Please formulate a CPP solution to the following problem:

Example

Input

crc
1


Output

crc

### Response

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

typedef long long ll;

const int N = 2e3 + 5;

struct A {
  int l;
  ll sum;
} dp[N][N];

char s[N];
char ans[2 * N];
int cn;
ll k;

int dfs(int l, int r) {
  if(dp[l][r].l != -1) return dp[l][r].l;
  if(l == r) {
    dp[l][r] = (A){1, 1}; return 1;
  }
  if(l > r) {
    dp[l][r] = (A){0, 1}; return 0;
  }
  if(s[l] == s[r]) {
    dp[l][r].l = dfs(l + 1, r - 1) + 2;
    dp[l][r].sum = dp[l+1][r-1].sum;
    return dp[l][r].l;
  }
  int la = dfs(l + 1, r);
  int ra = dfs(l, r - 1);
  dp[l][r].l = min(la, ra) + 2;
  if(la + 2 == dp[l][r].l) dp[l][r].sum += dp[l+1][r].sum;
  if(ra + 2 == dp[l][r].l) dp[l][r].sum += dp[l][r-1].sum;
  //cout << dp[l][r].sum << endl;
  if(dp[l][r].sum > k) dp[l][r].sum = k + 1;
  return dp[l][r].l;
}

void dfsn(int l, int r, int be) {
  if(l == r) {
    ans[be] = s[l]; return ;
  }
  if(l > r) return ;
  int len = dp[l][r].l;
  if(s[l] == s[r]) {
    ans[be] = ans[be+len-1] = s[l];
    dfsn(l+1, r-1, be+1); return ;
  }
  int la = dp[l+1][r].l;
  int lb = dp[l][r-1].l;
  if(la != dp[l][r].l-2) {
    ans[be] = ans[be+len-1] = s[r];
    //if(dp[l][r].l != lb+2) cout<<"error!"<<endl;
    //cout << be << " " << len << " " << s[r] << endl;
    dfsn(l, r-1, be+1); return ;
  } else
  if(lb != dp[l][r].l-2) {
    ans[be] = ans[be+len-1] = s[l];
    //cout << be << " " << len << " " << s[l] << endl;
    dfsn(l+1, r, be+1); return ;
  }
  //cout << dp[l+1][r].sum << " " << dp[l][r-1].sum << endl;
  if(s[l] < s[r]) {
    if(dp[l+1][r].sum >= k) {
      ans[be] = ans[be+len-1] = s[l];
      //cout << be << " " << len << " " << s[l] << endl;
      dfsn(l+1, r, be+1); return ;
    } else {
      ans[be] = ans[be+len-1] = s[r];
      k -= dp[l+1][r].sum;
      //cout << be << " " << len << " " << s[r] << endl;
      dfsn(l, r-1, be+1); return ;
    }
  } else if(s[l] > s[r]) {
    if(dp[l][r-1].sum >= k) {
      ans[be] = ans[be+len-1] = s[r];
      //cout << be << " " << len << " " << s[r] << endl;
      dfsn(l, r-1, be+1); return ;
    } else {
      ans[be] = ans[be+len-1] = s[l];
      k -= dp[l][r-1].sum;
      //cout << be << " " << len << " " << s[l] << endl;
      dfsn(l+1, r, be+1); return ;
    }
  }
}

int main() {
  //freopen("out", "w", stdout);
  scanf("%s%lld", s, &k);
  int len = strlen(s);
  for(int i = 0; i < len; ++ i)
    for(int j = 0; j < len; ++ j)
      dp[i][j].l = -1, dp[i][j].sum = 0;

  int m = dfs(0, len-1); cn = 0;
  //cout << dp[1][len-1].sum << endl;
  if(k > dp[0][len-1].sum) {
    puts("NONE"); return 0;
  }
  //cout << m << endl;
  dfsn(0, len-1, 0);
  ans[m] = '\n';
  printf("%s", ans);
  return 0;
}
/*
thdstodxtksrnfacdsohnlfuivqvqsozdstwaszmkboehgcerwxawuojpfuvlxxdfkezprodnettawsyqazekcftgqbrrtkzngaxzlnphynkmsdsdleqaxnhehwzgzwtldwaacfczqkfpvxnalnnhfzbagzhqhstcymdeijlbkbbubdnptolrmemfxlmmzhfpshykxvzbjmcnsusllpyqghzhdvljdxrrebeef
11469362357953500
*/

```