Example

Input

crc
1


Output

crc
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#define maxn 2020
using namespace std;
typedef long long LL;
char c[maxn];
LL f[maxn][maxn];
LL k;
int n;
int dp[maxn][maxn];
char ans[maxn*2];
int main()
{
    scanf("%s%lld",c+1,&k);
    n=strlen(c+1);
    for(int i=1;i<=n;++i)
    {
        dp[i][i]=0;
        f[i][i]=1;
    }
    for(int l=2;l<=n;++l)
        for(int i=1;i+l-1<=n;++i)
        {
            int j=i+l-1;
            if(c[i]==c[j])
            {
                dp[i][j]=dp[i+1][j-1];
                if(i+1>j-1) f[i][j]=1;
                else f[i][j]=f[i+1][j-1];
            }
            else
            {
                if(dp[i+1][j]+1<dp[i][j-1]+1)
                {
                    dp[i][j]=dp[i+1][j]+1;
                    f[i][j]=f[i+1][j];
                }
                else if(dp[i+1][j]+1==dp[i][j-1]+1)
                {
                    dp[i][j]=dp[i+1][j]+1;
                    f[i][j]=f[i+1][j]+f[i][j-1];
                    if(f[i][j]>k) f[i][j]=k;
                }
                else
                {
                    dp[i][j]=dp[i][j-1]+1;
                    f[i][j]=f[i][j-1];
                }
            }
        }
    if(f[1][n]<k) printf("NONE\n");
    else
    {
        LL m=k;
        int l=1,r=dp[1][n]+n,L=1,R=n;
        while(L<R)
        {
            if(c[L]==c[R])
            {
                ans[l]=c[L];
                ans[r]=c[R];
                l++;
                r--;
                L++;
                R--;
            }
            else
            {
                if(dp[L+1][R]+1<dp[L][R-1]+1)
                {
                    ans[r--]=c[L];
                    ans[l++]=c[L];
                    L++;
                }
                else if(dp[L+1][R]+1==dp[L][R-1]+1)
                {
                    if(c[L]<c[R])
                    {
                        if(f[L+1][R]>=m)
                        {
                            ans[r--]=c[L];
                            ans[l++]=c[L];
                            L++;
                        }
                        else
                        {
                            m-=f[L+1][R];
                            ans[r--]=c[R];
                            ans[l++]=c[R];
                            R--;
                        }
                    }
                    else
                    {
                        if(f[L][R-1]>=m)
                        {
                            ans[r--]=c[R];
                            ans[l++]=c[R];
                            R--;
                        }
                        else
                        {
                            m-=f[L][R-1];
                            ans[r--]=c[L];
                            ans[l++]=c[L];
                            L++;
                        }
                    }
                }
                else
                {
                    ans[r--]=c[R];
                    ans[l++]=c[R];
                    R--;
                }
            }
        }
        if(L==R) ans[l]=c[L];
    printf("%s\n",ans+1);
    }
    return 0;
}