問題文

（この問題は Codeforces Round #286 (Div. 2) の問題A の入力の制約を変更したものです。）

K氏が英小文字からなる文字列 $s$ をくれた。これに英小文字をちょうど一つ挿入して回文にしてほしいそうだ。
（回文とは、前から読んでも後ろから読んでも文字が同じ順番で出現するような文字列である。
例えば "noon", "testset", "a" はどれも回文であるが、 "test", "kitayuta" は回文ではない。）

挿入する文字としてどの英小文字を使ってもよく、それを $s$ のどの位置に挿入してもよい。
$s$ の先頭や末尾への挿入も可能である。
与えられた文字列 $s$ がすでに回文であっても、一文字を挿入しなくてはならない。

$s$ に英小文字を一つ挿入し、その結果文字列を回文にすることが可能ならば、そのようにして得られる回文を一つ出力せよ。
そうでなければ、 "NA" （引用符除く）と大文字で出力せよ。
得られる回文が複数存在する場合は、そのうちどれを出力してもよい。

入力

$s$

• $1 \le |s| \le 10^5$
• $s$ の各文字は英小文字である。

出力

$s$ に英小文字を一つ挿入して回文にすることが可能ならば、そのようにして得られる回文を一つ出力せよ。
そうでなければ、 "NA" （引用符除く）と大文字で出力せよ。
複数の解が存在する場合は、そのうちどれを出力しても正答となる。

サンプル

revive

reviver

ee

eye

kitayuta

NA