#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
//#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define NUM 2005
#define BIG_NUM 1000000000000000005

ll LEN[NUM][NUM];
ll dp[NUM][NUM];
string line;

ll calc(ll &A,ll B){

	return min(A+B,2*(ll)BIG_NUM);
}

int main(){

	cin >> line;

	int length;
	for(length = 0; line[length] != '\0'; length++);

	for(int i = 0; i < length; i++){
		for(int k = 0; k < length; k++){
			LEN[i][k] = BIG_NUM;
			dp[i][k] = 0;
		}
	}

	ll K;
	scanf("%lld",&K);

	for(int i = length-1; i >= 0; i--){

		LEN[i][i] = 1;

		for(int k = i+1; k < length; k++){
			if(line[i] == line[k]){
				if(k == i+1){

					LEN[i][k] = 2;

				}else{

					LEN[i][k] = LEN[i+1][k-1]+2;
				}
			}
			LEN[i][k] = min(LEN[i][k],min(LEN[i][k-1],LEN[i+1][k])+2);
		}
	}

	for(int i = length-1; i >= 0; i--){

		dp[i][i] = 1;

		for(int k = i+1; k < length; k++){

			if(line[i] == line[k]){
				if(k == i+1){

					dp[i][k] = calc(dp[i][k],1);
				}else{

					dp[i][k] = calc(dp[i][k],dp[i+1][k-1]);
				}

			}else{

				if(LEN[i][k-1] < LEN[i+1][k]){

					dp[i][k] = calc(dp[i][k],dp[i][k-1]);

				}else if(LEN[i][k-1] > LEN[i+1][k]){

					dp[i][k] = calc(dp[i][k],dp[i+1][k]);

				}else{

					dp[i][k] = calc(dp[i][k],dp[i][k-1]+dp[i+1][k]);
				}
			}
		}
	}

	if(dp[0][length-1] < K){
		printf("NONE\n");
		return 0;
	}

	ll count = 1,tmp;
	int left = 0,right = length-1;
	string L = "";

	while(left < right){

		if(line[left] == line[right]){

			L += line[left];
			left++;
			right--;

		}else{ //line[left] != line[right]

			if(LEN[left][right-1] < LEN[left+1][right]){

				L += line[right];
				right--;

			}else if(LEN[left][right-1] > LEN[left+1][right]){

				L += line[left];
				left++;

			}else{

				tmp = count;

				if(line[left] < line[right]){

					tmp += dp[left+1][right];
				}else{
					tmp += dp[left][right-1];
				}

				if((tmp > K && line[left] < line[right]) || (tmp <= K && line[left] >= line[right])){

					L += line[left];
					left++;

				}else{

					L += line[right];
					right--;
				}
				if(tmp <= K){

					count = tmp;
				}
			}
		}
	}

	string R = L;
	reverse(R.begin(),R.end());

	if(left == right){
		L += line[left];
	}

	string ans = L+R;

	printf("%s\n",ans.c_str());

	return 0;
}


### Prompt

Please create a solution in CPP to the following problem:

Example

Input

crc
1


Output

crc

### Response

```cpp
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
//#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define NUM 2005
#define BIG_NUM 1000000000000000005

ll LEN[NUM][NUM];
ll dp[NUM][NUM];
string line;

ll calc(ll &A,ll B){

	return min(A+B,2*(ll)BIG_NUM);
}

int main(){

	cin >> line;

	int length;
	for(length = 0; line[length] != '\0'; length++);

	for(int i = 0; i < length; i++){
		for(int k = 0; k < length; k++){
			LEN[i][k] = BIG_NUM;
			dp[i][k] = 0;
		}
	}

	ll K;
	scanf("%lld",&K);

	for(int i = length-1; i >= 0; i--){

		LEN[i][i] = 1;

		for(int k = i+1; k < length; k++){
			if(line[i] == line[k]){
				if(k == i+1){

					LEN[i][k] = 2;

				}else{

					LEN[i][k] = LEN[i+1][k-1]+2;
				}
			}
			LEN[i][k] = min(LEN[i][k],min(LEN[i][k-1],LEN[i+1][k])+2);
		}
	}

	for(int i = length-1; i >= 0; i--){

		dp[i][i] = 1;

		for(int k = i+1; k < length; k++){

			if(line[i] == line[k]){
				if(k == i+1){

					dp[i][k] = calc(dp[i][k],1);
				}else{

					dp[i][k] = calc(dp[i][k],dp[i+1][k-1]);
				}

			}else{

				if(LEN[i][k-1] < LEN[i+1][k]){

					dp[i][k] = calc(dp[i][k],dp[i][k-1]);

				}else if(LEN[i][k-1] > LEN[i+1][k]){

					dp[i][k] = calc(dp[i][k],dp[i+1][k]);

				}else{

					dp[i][k] = calc(dp[i][k],dp[i][k-1]+dp[i+1][k]);
				}
			}
		}
	}

	if(dp[0][length-1] < K){
		printf("NONE\n");
		return 0;
	}

	ll count = 1,tmp;
	int left = 0,right = length-1;
	string L = "";

	while(left < right){

		if(line[left] == line[right]){

			L += line[left];
			left++;
			right--;

		}else{ //line[left] != line[right]

			if(LEN[left][right-1] < LEN[left+1][right]){

				L += line[right];
				right--;

			}else if(LEN[left][right-1] > LEN[left+1][right]){

				L += line[left];
				left++;

			}else{

				tmp = count;

				if(line[left] < line[right]){

					tmp += dp[left+1][right];
				}else{
					tmp += dp[left][right-1];
				}

				if((tmp > K && line[left] < line[right]) || (tmp <= K && line[left] >= line[right])){

					L += line[left];
					left++;

				}else{

					L += line[right];
					right--;
				}
				if(tmp <= K){

					count = tmp;
				}
			}
		}
	}

	string R = L;
	reverse(R.begin(),R.end());

	if(left == right){
		L += line[left];
	}

	string ans = L+R;

	printf("%s\n",ans.c_str());

	return 0;
}


```