#include <string>
#include <vector>
using namespace std;

// 演算法同 C 版：只構造左半邊，貪心逐位，用多重集合排列數定位第 k 個。
// Same as the C version: build only the left half, greedy per position,
// using multinomial counts (capped) to locate the k-th arrangement.
class Solution {
    // 計算 r!/∏cnt!，超過 cap 就封頂 / multinomial r!/∏cnt!, clamped at cap
    long long multinomial(vector<int>& cnt, long long cap) {
        long long perm = 1, used = 0;        // perm 排列數, used 已放入數 / running count and items placed
        for (int c = 0; c < 26; c++)
            for (int j = 1; j <= cnt[c]; j++) {
                used++;                      // 多放一個字元 / one more item
                perm = perm * used / j;      // 逐步搭出組合數（保持整數） / build binomials, stays integer
                if (perm > cap) return cap + 1;  // 封頂避免溢位 / clamp to avoid overflow
            }
        return perm;
    }
public:
    string smallestPalindrome(string s, int k) {
        int n = s.size();
        vector<int> cnt(26, 0);              // vector 是可變長度陣列 / vector is a growable array
        for (char ch : s) cnt[ch - 'a']++;   // range-for 走訪每個字元 / range-for over each char

        vector<int> half(26);                // 左半邊可用次數 / usable half counts
        int oddChar = -1;                    // 中間字元 / the middle (odd-count) letter
        for (int c = 0; c < 26; c++) {
            if (cnt[c] & 1) oddChar = c;     // 判斷奇偶 / test oddness
            half[c] = cnt[c] / 2;            // 取一半 / take half
        }
        int h = n / 2;                       // 左半邊長度 / left-half length
        long long cap = 1000000;             // k <= 1e6 的封頂 / cap for k <= 1e6

        // 總排列數不足 k 就回空字串 / not enough distinct palindromes → ""
        if (multinomial(half, cap) < k) return "";

        string first(h, ' ');                // 左半邊字串，先填佔位 / left half, placeholder-filled
        for (int pos = 0; pos < h; pos++) {
            for (int c = 0; c < 26; c++) {   // 由小到大試字母 / smallest letter first
                if (half[c] == 0) continue;  // 用完就跳過 / skip exhausted letters
                half[c]--;                   // 試放 c / tentatively place c
                long long ways = multinomial(half, cap);  // 剩餘排列數 / arrangements of remainder
                if (ways >= k) {             // 第 k 個在此分支 / the k-th is here
                    first[pos] = 'a' + c;    // 固定 c / commit c
                    break;
                }
                k -= ways;                   // 跳過此分支 / skip this branch's ways
                half[c]++;                   // 還原 / undo
            }
        }

        string res = first;                          // 左半邊 / left half
        if (oddChar >= 0) res += char('a' + oddChar);// 有奇數字元放中間 / middle char if present
        // string(rbegin, rend) 是反轉字串 / reversed copy via reverse iterators
        res += string(first.rbegin(), first.rend()); // 右半邊為左半鏡像 / right half mirrors left
        return res;
    }
};