#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using int64 = long long;
string S;
ll k;

const ll INF = 1e18 + 10;
ll dp1[2010][2010];
ll dp2[2010][2010];

ll f1(int h, int t) {
	if (h >= t)
		return 0;
	ll& d = dp1[h][t];
	if (d != -1)
		return d;

	d = INF;
	if (S[h] != S[t]) {
		d = min(f1(h + 1, t) + 1, f1(h, t - 1) + 1);
	} else {
		d = f1(h + 1, t - 1);
	}
	return d;
}

ll f2(int h, int t) {
	if (h >= t)
		return 1;

	ll& d = dp2[h][t];
	if (d != -1)
		return d;

	d = 0;
	if (S[h] == S[t]) {
		d = f2(h + 1, t - 1);
	} else {
		if (dp1[h][t] == f1(h + 1, t) + 1) {
			d += f2(h + 1, t);
		}
		if (dp1[h][t] == f1(h, t - 1) + 1) {
			d += f2(h, t - 1);
		}
	}
	return d = min(INF, d);
}

int main() {
	cin >> S >> k;
	//k--;
	int N = S.size();

	memset(dp1, -1, sizeof dp1);
	memset(dp2, -1, sizeof dp2);
	int len = f1(0, N - 1);

	//cout << len << endl;

	ll sum = f2(0, N - 1);
	if (k > sum) {
		cout << "NONE" << endl;
		return 0;
	}

	string ans;
	int h = 0, t = N - 1;
	for (int i = 0; i < (N + len) / 2; i++) {
		for (char c = 'a'; c <= 'z'; c++) {
			int nh = h + (S[h] == c);
			int nt = t - (S[t] == c);
			int d = (S[h] != c) + (S[t] != c);
			if (dp1[h][t] != f1(nh, nt) + d)
				continue;
			ll num = f2(nh, nt);
			assert(num != 0);
			if (num >= k) {
				ans += c;
				h = nh, t = nt;
				break;
			} else {
				k -= num;
			}
		}
	}

	if (h == t) {
		string ss = ans;
		reverse(ss.begin(), ss.end());
		ans += S[h] + ss;
	} else {
		string ss = ans;
		reverse(ss.begin(), ss.end());
		ans += ss;
	}

	cout << ans << endl;

	return 0;
}
### 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;
using int64 = long long;
string S;
ll k;

const ll INF = 1e18 + 10;
ll dp1[2010][2010];
ll dp2[2010][2010];

ll f1(int h, int t) {
	if (h >= t)
		return 0;
	ll& d = dp1[h][t];
	if (d != -1)
		return d;

	d = INF;
	if (S[h] != S[t]) {
		d = min(f1(h + 1, t) + 1, f1(h, t - 1) + 1);
	} else {
		d = f1(h + 1, t - 1);
	}
	return d;
}

ll f2(int h, int t) {
	if (h >= t)
		return 1;

	ll& d = dp2[h][t];
	if (d != -1)
		return d;

	d = 0;
	if (S[h] == S[t]) {
		d = f2(h + 1, t - 1);
	} else {
		if (dp1[h][t] == f1(h + 1, t) + 1) {
			d += f2(h + 1, t);
		}
		if (dp1[h][t] == f1(h, t - 1) + 1) {
			d += f2(h, t - 1);
		}
	}
	return d = min(INF, d);
}

int main() {
	cin >> S >> k;
	//k--;
	int N = S.size();

	memset(dp1, -1, sizeof dp1);
	memset(dp2, -1, sizeof dp2);
	int len = f1(0, N - 1);

	//cout << len << endl;

	ll sum = f2(0, N - 1);
	if (k > sum) {
		cout << "NONE" << endl;
		return 0;
	}

	string ans;
	int h = 0, t = N - 1;
	for (int i = 0; i < (N + len) / 2; i++) {
		for (char c = 'a'; c <= 'z'; c++) {
			int nh = h + (S[h] == c);
			int nt = t - (S[t] == c);
			int d = (S[h] != c) + (S[t] != c);
			if (dp1[h][t] != f1(nh, nt) + d)
				continue;
			ll num = f2(nh, nt);
			assert(num != 0);
			if (num >= k) {
				ans += c;
				h = nh, t = nt;
				break;
			} else {
				k -= num;
			}
		}
	}

	if (h == t) {
		string ss = ans;
		reverse(ss.begin(), ss.end());
		ans += S[h] + ss;
	} else {
		string ss = ans;
		reverse(ss.begin(), ss.end());
		ans += ss;
	}

	cout << ans << endl;

	return 0;
}
```