#include #include #include using namespace std; struct State { int fpos; int rpos; bool inserted; string result; }; string s; string ConstructPalindrome(string str, State& st) { // もともと奇数だった場合は偶数になる string result = st.result, temp = st.result; reverse(temp.begin(), temp.end()); if (str.size() % 2 == 1) { result += temp; } else { if (!st.inserted) { result.pop_back(); temp.pop_back(); result.push_back('a'); } else result.pop_back(); result += temp; } return result; } string AppendChar(string str, char c) { str.push_back(c); return str; } void Solve() { string forward, reversed, temp = s; forward = temp; reverse(temp.begin(), temp.end()); reversed = temp; queue que; que.push((State){0, 0, false, ""}); while (!que.empty()) { State st = que.front(); que.pop(); // printf("fpos %d rpos %d inserted %d result %s\n", st.fpos, st.rpos, st.inserted, st.result.c_str()); // 半分まで調べればよい if (st.fpos > forward.size() / 2 || st.rpos > reversed.size() / 2) { cout << ConstructPalindrome(s, st) << endl; return; } if (forward[st.fpos] == reversed[st.rpos]) { que.push((State){st.fpos + 1, st.rpos + 1, st.inserted, AppendChar(st.result, forward[st.fpos])}); } else if (!st.inserted) { que.push((State){st.fpos, st.rpos + 1, true, AppendChar(st.result, reversed[st.rpos])}); que.push((State){st.fpos + 1, st.rpos, true, AppendChar(st.result, forward[st.fpos])}); } } cout << "NA" << endl; } int main() { cin >> s; Solve(); return 0; }