Problem Statement

(This problem is Problem A of Codeforces Round #286 (Div. 2) with modified input constraints.)

Mr. K gave you a string $s$ consisting of lowercase English letters. He wants you to insert exactly one lowercase English letter into it to make it a palindrome.
(A palindrome is a string in which the characters appear in the same order whether read from the front or from the back.
For example, "noon", "testset", and "a" are all palindromes, but "test" and "kitayuta" are not.)

You may choose any lowercase English letter as the character to insert, and you may insert it at any position in $s$.
Insertion at the beginning or the end of $s$ is also allowed.
Even if the given string $s$ is already a palindrome, you must insert one character.

If it is possible to insert one lowercase English letter into $s$ so that the resulting string is a palindrome, output one palindrome obtainable in this way.
Otherwise, output "NA" (without quotes) in uppercase.
If there are multiple obtainable palindromes, you may output any of them.

Input

$s$

• $1 \le |s| \le 10^5$
• Each character of $s$ is a lowercase English letter.

Output

If it is possible to make $s$ a palindrome by inserting one lowercase English letter, output one palindrome obtainable in this way.
Otherwise, output "NA" (without quotes) in uppercase.
If there are multiple solutions, any of them will be accepted.

Sample

revive

reviver

ee

eye

kitayuta

NA