Mr. Kitayuta has kindly given you a string s consisting of lowercase English letters. You are asked to insert exactly one lowercase English letter into s to make it a palindrome. A palindrome is a string that reads the same forward and backward. For example, "noon", "testset" and "a" are all palindromes, while "test" and "kitayuta" are not.

You can choose any lowercase English letter, and insert it to any position of s, possibly to the beginning or the end of s. You have to insert a letter even if the given string is already a palindrome.

If it is possible to insert one lowercase English letter into s so that the resulting string will be a palindrome, print the string after the insertion. Otherwise, print "NA" (without quotes, case-sensitive). In case there is more than one palindrome that can be obtained, you are allowed to print any of them.


-----Input-----

The only line of the input contains a string s (1 ≤ |s| ≤ 10). Each character in s is a lowercase English letter.


-----Output-----

If it is possible to turn s into a palindrome by inserting one lowercase English letter, print the resulting string in a single line. Otherwise, print "NA" (without quotes, case-sensitive). In case there is more than one solution, any of them will be accepted. 


-----Examples-----
Input
revive

Output
reviver

Input
ee

Output
eye
Input
kitayuta

Output
NA



-----Note-----

For the first sample, insert 'r' to the end of "revive" to obtain a palindrome "reviver".

For the second sample, there is more than one solution. For example, "eve" will also be accepted.

For the third sample, it is not possible to turn "kitayuta" into a palindrome by just inserting one letter.

Source: codeforces | Difficulty: EASY
Tags: String algorithms

Implementation

Complete search


Solutions:
import sys
s = input().strip()

def isPalin(n):
	if n[::-1] == n:
		return True
	return False
for i in range(len(s) + 1):
	for j in 'abcdefghijklmnopqrstuvwxyz':
		if isPalin(s[:i] + j + s[i:]):
			print(s[:i] + j + s[i:])
			sys.exit(0)
print('NA')


def is_palindrome(s):
	return str(s) == str(s)[::-1]

def convert_palindrome(s):
	if s[0] == s[-1]:
		sub_palindrome = convert_palindrome(s[1:-1])
		if sub_palindrome is None:
			return None
		else:
			return s[0] + sub_palindrome + s[-1]
	elif is_palindrome(s + s[0]):
		return s + s[0]
	elif is_palindrome(s[-1] + s):
		return s[-1] + s
	else:
		return None

def main():
	s = input()
	length = len(s)
	if is_palindrome(s):
		if length % 2 == 0:
			mid = length // 2
			print(s[:mid] + 'a' + s[mid:])
		else:
			mid = (length - 1) // 2
			print(s[:mid] + s[mid] + s[mid:])
	else:
		new_palindrome = convert_palindrome(s)
		if new_palindrome is None:
			print('NA')
		else:
			print(new_palindrome)
main()


def is_palindrome(s):
	s = list(s)
	s1 = s.copy()
	s1.reverse()
	return s == s1
s = input()
n = len(s)
flag = True
if is_palindrome(s):
	s1 = s[:n // 2]
	s2 = s[n // 2:]
	s = s1 + s[n // 2] + s2
else:
	l = 0
	r = n - 1
	while l < r:
		if s[l] == s[r]:
			l += 1
			r -= 1
		else:
			s1 = s[l + 1:r + 1]
			s2 = s[l:r]
			if is_palindrome(s1):
				pre = s[:l + 1]
				post = s[r + 1:]
				s = pre + s1 + s[l] + post
			elif is_palindrome(s2):
				pre = s[:l]
				post = s[r:]
				s = pre + s[r] + s2 + post
			else:
				flag = False
			break
if flag:
	print(s)
else:
	print('NA')


def isPalindrome(s):
	return s[:] == s[::-1]
st = input()
i = 0
for i in range(int(len(st) / 2)):
	if st[i] != st[len(st) - i - 1]:
		break
size = len(st)
k = st[:i] + f'{st[size - i - 1]}' + st[i:]
s1 = st[:size - i] + f'{st[i]}' + st[len(st) - i:]
s2 = st[:int(size / 2) + 1] + f'{st[int(size / 2)]}' + st[int(size / 2) + 1:]
if isPalindrome(st):
	print(s2)
elif isPalindrome(k):
	print(k)
elif isPalindrome(s1):
	print(s1)
else:
	print('NA')


a = input()

def isPalindrome(word):
	if len(word) % 2 == 0:
		mid = int(len(word) / 2)
		return word[:mid] == word[mid:][::-1]
	else:
		mid = int(len(word) / 2)
		return word[:mid] == word[mid + 1:][::-1]
ok = 0
for k in range(len(a) + 1):
	for i in range(26):
		word = a[:k] + chr(ord('a') + i) + a[k:]
		if isPalindrome(word):
			ok = 1
			print(word)
			break
	if ok:
		break
if not ok:
	print('NA')


s = input()

def check(a):
	n = len(a)
	for i in range(n // 2):
		if a[i] != a[n - i - 1]:
			return False
	return True
import sys
for i in range(26):
	x = chr(ord('a') + i)
	for i in range(len(s) + 1):
		if check(s[:i] + x + s[i:]):
			print(s[:i] + x + s[i:])
			sys.exit(0)
print('NA')


s = input()
for i in range(len(s) + 1):
	for j in range(26):
		z = s[:i] + chr(ord('a') + j) + s[i:]
		if z == z[::-1]:
			print(z)
			exit(0)
print('NA')


s = input()
for i in range(26):
	for j in range(len(s) + 1):
		ans = s[:j] + chr(97 + i) + s[j:]
		if ans == ans[::-1]:
			print(ans)
			exit()
print('NA')


def makePalindrome(st):
	if not st or not st.isalpha() or (not st.islower()):
		return 'NA'
	chars = 'abcdefghijklmnopqrstuvwxyz'
	for letter in chars:
		for pos in range(0, len(st) + 1):
			tmp = st[:pos] + letter + st[pos:]
			if isPalindrome(tmp):
				return tmp
	return 'NA'

def isPalindrome(st):
	(i, j) = (0, len(st) - 1)
	while i < j:
		if st[i] != st[j]:
			return False
		i += 1
		j -= 1
	return True
st = input()
print(makePalindrome(st))


def ispalindrome(t, k):
	global i
	for i in range(k // 2):
		if t[i] != t[-1 - i]:
			return False
	return True
s = list(input())
l = len(s)
x = l // 2
if ispalindrome(s, l):
	s.insert(x, s[x])
	print(''.join(s))
else:
	first = s.copy()
	second = s.copy()
	first.insert(i, s[-1 - i])
	second.insert(-1 - i, s[i])
	(second[-1 - i], second[-2 - i]) = (second[-2 - i], second[-1 - i])
	if ispalindrome(first, l + 1):
		print(''.join(first))
	elif ispalindrome(second, l + 1):
		print(''.join(second))
	else:
		print('NA')


n = list(input())
for i in 'abcdefghijklmnopqrstuvwxyz':
	for j in range(0, len(n) + 1):
		w = n[:]
		w.insert(j, i)
		if w == w[::-1]:
			print(''.join(w))
			quit()
print('NA')


s = input()
s1 = s[::-1]
p = False

def try1(a):
	q = s[:a] + s1[a] + s[a:]
	q1 = q[::-1]
	for i in range(a + 1, len(q) // 2):
		if q[i] != q1[i]:
			return False
	return True

def try2(a):
	q = s[:len(s) - a] + s[a] + s[len(s) - a:]
	q1 = q[::-1]
	for i in range(a + 1, len(q) // 2):
		if q[i] != q1[i]:
			return False
	return True
for i in range(len(s) // 2):
	if s[i] != s1[i]:
		if try1(i):
			q = s[:i] + s1[i] + s[i:]
			print(q)
			exit(0)
		elif try2(i):
			q = s[:len(s) - i] + s[i] + s[len(s) - i:]
			print(q)
			exit(0)
		else:
			p = True
			break
if p:
	print('NA')
else:
	d = s[:len(s) // 2] + s[len(s) // 2] + s[len(s) // 2:]
	print(d)


def pal(a):
	n = len(a)
	for i in range(n // 2):
		if a[i] != a[n - 1 - i]:
			return False
	return True
s = input()
alp = 'abcdefghijklmnopqrstuvwxyz'
ans = 'NA'
for i in range(len(s) + 1):
	for j in alp:
		if pal(s[:i] + j + s[i:]):
			ans = s[:i] + j + s[i:]
			break
print(ans)


palindrom = lambda s: s == s[::-1]
printans = lambda l: print(''.join(l))
s = list(input())
for i in range(len(s) + 1):
	for letter in 'abcdefghijklmnopqrstvwuxyz':
		tmp = s[:]
		tmp.insert(i, letter)
		if palindrom(tmp):
			printans(tmp)
			exit()
print('NA')


def ch(a):
	a = list(a)
	i = 0
	while i < len(a) // 2 + 1:
		if a[i] != a[len(a) - i - 1]:
			return 0
		i += 1
	return 1
a = list(input())
i = 0
d = 1
while i < len(a):
	c = a[i]
	j = 0
	while j <= len(a):
		a.insert(j, c)
		if ch(a):
			d = ''.join(a)
		a.pop(j)
		j += 1
	if d != 1:
		break
	i += 1
if d != 1:
	print(d)
else:
	print('NA')


def solve(w):
	if w == ''.join(reversed(w)):
		return w[:len(w) // 2] + w[len(w) // 2] + w[len(w) // 2:]
	for v in (w, ''.join(reversed(w))):
		(i, j, c) = (0, len(w) - 1, -1)
		while i < j:
			if v[i] != v[j]:
				if c != -1:
					(i, j, c) = (-1, -1, -1)
					break
				else:
					c = j
					i += 1
			else:
				i += 1
				j -= 1
		if c != -1:
			return v[:c + 1] + v[len(v) - 1 - c] + v[c + 1:]
	return 'NA'
print(solve(input()))


def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def MAP2():
	return map(float, input().split())

def LIST():
	return list(map(int, input().split()))

def STRING():
	return input()
import string
from heapq import heappop, heappush
from bisect import *
from collections import deque, Counter
from math import *
from itertools import permutations, accumulate
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def solve(s):
	if s == s[::-1]:
		return True
	return False
s = STR()
i = 0
ans = 1
while i < len(s):
	x = s[i]
	j = 0
	while j <= len(s):
		s.insert(j, x)
		if solve(s):
			ans = ''.join(s)
		s.pop(j)
		j += 1
	if ans != 1:
		break
	i += 1
if ans != 1:
	print(ans)
else:
	print('NA')


from string import ascii_lowercase

def check(s):
	return s == s[::-1]
s = input()
for i in range(len(s) + 1):
	for c in ascii_lowercase:
		if check(s[:i] + c + s[i:]):
			print(s[:i] + c + s[i:])
			exit()
print('NA')


def ispal(x):
	if len(x) == 1:
		return True
	if len(x) == 2:
		return x[0] == x[1]
	if x[0] != x[-1]:
		return False
	return ispal(x[1:len(x) - 1])
ct = 0
a = input()
l = len(a)
x = ''
y = ''
for i in range(l // 2):
	if a[i] != a[-(i + 1)]:
		x = a[:i] + a[-(i + 1)] + a[i:]
		y = a[:l - i] + a[i] + a[l - i:]
		break
if x == '' and y == '':
	if l % 2 == 1:
		print(a[:l // 2] + a[l // 2] * 2 + a[l // 2 + 1:])
		quit()
	else:
		print(a[:l // 2] + 'y' + a[l // 2:])
		quit()
if ispal(x):
	print(x)
	quit()
if ispal(y):
	print(y)
	quit()
else:
	print('NA')


s = input()
n = len(s)
for i in range(n + 1):
	new_s = s[:i] + s[-i - (i <= n // 2)] + s[i:]
	if new_s == new_s[::-1]:
		print(new_s)
		break
else:
	print('NA')


s = input()
lens = len(s)
flag = 0
for i in range(0, lens + 1):
	for j in range(ord('a'), ord('z') + 1):
		s1 = s
		s1 = s[:i] + chr(j) + s[i:]
		s2 = s1[::-1]
		if s1 == s2:
			print(s1)
			flag = 1
			break
	if flag == 1:
		break
if flag == 0:
	print('NA')


s = list(input())
n = len(s)
candidates = [s + ['.']]
res = 'NA'
for i in range(n):
	candidates.append(s[:i] + ['.'] + s[i:])
for s in candidates:
	legal = True
	for i in range((n + 1) // 2):
		if s[i] == s[-i - 1] or s[i] == '.' or s[-i - 1] == '.':
			continue
		legal = False
	if legal:
		res = s
if res != 'NA':
	for i in range((n + 1) // 2):
		if res[i] == '.':
			res[i] = res[-i - 1]
		elif res[-i - 1] == '.':
			res[-i - 1] = res[i]
	res = [s if s != '.' else 'a' for s in res]
	res = ''.join(res)
print(res)


s = input()
l = len(s)
a = 'abcdefghijklmnopqrstuvwxyz'
for i in range(len(a)):
	for j in range(l + 1):
		x = s[:j] + a[i] + s[j:]
		if x == x[::-1]:
			print(x)
			exit()
else:
	print('NA')


def is_palindrome(s):
	return s == s[::-1]
s = input()
letters = set(s)
found = False
for letter in letters:
	for i in range(len(s) + 1):
		temp = s[:i] + letter + s[i:]
		if is_palindrome(temp):
			print(temp)
			found = True
			break
	if found:
		break
if not found:
	print('NA')


def is_palindrome(s):
	if s == s[::-1]:
		return True
	return False
s = input().strip()
l = len(s)
if is_palindrome(s):
	if l % 2:
		print(s[:l // 2] + s[l // 2] + s[l // 2:])
	else:
		print(s[:l // 2] + 'a' + s[l // 2:])
else:
	for i in range(l):
		if is_palindrome(s[:i] + s[i + 1:]):
			k = l - i - 1
			if i < l // 2:
				k += 1
			c = s[:k] + s[i] + s[k:]
			if is_palindrome(c):
				print(c)
				break
	else:
		print('NA')


def palin(sr):
	sr1 = sr[::-1]
	return sr == sr1
s = input()
i = 0
j = len(s) - 1
if j == 0:
	print(s * 2)
else:
	while i < j and s[i] == s[j]:
		i = i + 1
		j = j - 1
	if i < j:
		s1 = s[0:i] + s[j] + s[i:j + 1] + s[j + 1:]
		s2 = s[0:i] + s[i:j + 1] + s[i] + s[j + 1:]
		if palin(s1) or palin(s2):
			if palin(s1) and palin(s2) == False:
				print(s1)
			if palin(s2) and palin(s1) == False:
				print(s2)
			if palin(s1) and palin(s2):
				print(s1)
		else:
			print('NA')
	if i == j:
		s4 = s[0:i] + s[i] + s[i] + s[j + 1:]
		print(s4)
	if i > j:
		s3 = s[0:i] + 'a' + s[j + 1:]
		print(s3)


def ptest(l):
	m = l[:]
	m.reverse()
	if m == l:
		return True
	return False
a = input()
a = list(a)
lett = set(a)
done = False
for x in range(len(a) + 1):
	b = a[:]
	for t in lett:
		c = b[:x] + [t] + b[x:]
		c.reverse()
		if ptest(c):
			done = True
			print(''.join(c))
			break
	if done:
		break
if not done:
	print('NA')


s = list(input())
se = set(s)
ans = False
for i in range(11):
	for j in se:
		st = s.copy()
		st.insert(i, j)
		if st == st[::-1]:
			ans = True
			break
	if ans:
		break
if ans:
	print(''.join(st))
else:
	print('NA')


import sys
s = input()
list_s = list(s)
if s + s[0] == s[0] + s[::-1]:
	print(s + s[0])
	sys.exit()
else:
	for y in range(len(s)):
		letter = s[y]
		for x in range(len(s)):
			polindrom = list_s[:x] + [letter] + list_s[x:]
			if polindrom == polindrom[::-1]:
				print(''.join(polindrom))
				sys.exit()
print('NA')


s = input()
n = len(s)
for i in range(n + 1):
	for j in range(26):
		k = s[0:i] + chr(j + 97) + s[i:n]
		if k == k[::-1]:
			print(k)
			exit(0)
print('NA')


s = input()
si = s[::-1]
if s == si and len(s) % 2 == 0:
	output = s[:len(s) // 2] + 'a' + s[len(s) // 2:]
	print(output)
elif s == si and len(s) % 2 == 1:
	output = s[:len(s) // 2 + 1] + s[len(s) // 2:]
	print(output)
else:
	output = ''
	save = -1
	for i in range(len(s)):
		if s[i] != si[i]:
			output += s[i]
			save = i
			break
		else:
			output += s[i]
	if save > -1 and save < len(s):
		output += si[save:]
	if output != output[::-1]:
		output = ''
		save = -1
		for i in range(len(s)):
			if s[i] != si[i]:
				output += si[i]
				save = i
				break
			else:
				output += si[i]
		if save > -1 and save < len(s):
			output += s[save:]
		if output != output[::-1]:
			print('NA')
		else:
			print(output)
	else:
		print(output)


from math import floor
s = input()
ls = len(s)
if ls == 1:
	print(s + s)
	exit()
for i in range(floor(ls / 2)):
	isp = 0
	if s[i] != s[ls - i - 1]:
		isp = 1
		sn = s[:i] + s[ls - i - 1] + s[i:]
		csn = 0
		for j in range(floor(len(sn) / 2)):
			if sn[j] != sn[-j - 1]:
				csn = 1
				break
		if csn:
			csn = 0
			sn = s[:ls - i] + s[i] + s[ls - i:]
			for j in range(floor(len(sn) / 2)):
				if sn[j] != sn[-j - 1]:
					csn = 1
					break
		break
if isp:
	if csn:
		print('NA')
	else:
		print(sn)
elif ls % 2 == 1:
	print(s[:floor(ls / 2)] + s[floor(ls / 2)] + s[floor(ls / 2):])
else:
	print(s[:floor(ls / 2)] + 'a' + s[floor(ls / 2):])


s = input()
s = list(s)
t = []
t[:] = s[:]
l = len(s)
if s[:] == s[::-1]:
	if l % 2 == 0:
		s.insert(l // 2, 'a')
	else:
		s.insert(l // 2, s[l // 2])
	for j in range(len(s)):
		print(s[j], end='')
else:
	f = 0
	f1 = 0
	temp = 0
	temp1 = 0
	for j in range(l // 2):
		if s[j] == s[l - j - 1]:
			continue
		else:
			temp = j
			temp1 = s[j]
			temp2 = s[l - j - 1]
			break
	s.insert(l - temp, temp1)
	t.insert(temp, temp2)
	if s[:] != s[::-1]:
		f = 1
	if t[:] != t[::-1]:
		f1 = 1
	if f == 1 and f1 == 1:
		print('NA')
	elif f == 1:
		for j in range(len(t)):
			print(t[j], end='')
	elif f1 == 1:
		for j in range(len(s)):
			print(s[j], end='')
	else:
		for j in range(len(s)):
			print(s[j], end='')


s = str(input())

def ispalindrome(s):
	if s == s[::-1]:
		return True
	return False
for i in range(len(s) + 1):
	if i < len(s) / 2:
		t = s[:i] + s[len(s) - i - 1] + s[i:]
	else:
		t = s[:i] + s[len(s) - i] + s[i:]
	if ispalindrome(t):
		print(t)
		quit()
print('NA')


s = input()
for i in range(len(s) + 1):
	for j in range(97, 123):
		q = s[:i] + chr(j) + s[i:]
		if q == q[::-1]:
			print(q)
			exit()
print('NA')


from string import ascii_lowercase
s = input()
n = len(s)
for i in range(n + 1):
	for char in ascii_lowercase:
		new_s = s[:i] + char + s[i:]
		if new_s == new_s[::-1]:
			print(new_s)
			exit()
print('NA')


from math import *
from sys import stdin, stdout
import itertools
import os
import sys
import threading
from collections import deque, Counter, OrderedDict, defaultdict
from heapq import *
from fractions import Fraction
mod = int(pow(10, 9) + 7)

def ii():
	return int(input())

def si():
	return str(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def fii():
	return int(stdin.readline())

def fsi():
	return str(stdin.readline())

def fmi():
	return map(int, stdin.readline().split())

def fli():
	return list(fmi())
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
graph = defaultdict(list)
visited = [0] * 1000000
col = [-1] * 1000000

def bfs(d, v):
	q = []
	q.append(v)
	visited[v] = 1
	while len(q) != 0:
		x = q[0]
		q.pop(0)
		for i in d[x]:
			if visited[i] != 1:
				visited[i] = 1
				q.append(i)
		print(x)

def make_graph(e):
	d = {}
	for i in range(e):
		(x, y) = mi()
		if x not in d:
			d[x] = [y]
		else:
			d[x].append(y)
		if y not in d:
			d[y] = [x]
		else:
			d[y].append(x)
	return d

def gr2(n):
	d = defaultdict(list)
	for i in range(n):
		(x, y) = mi()
		d[x].append(y)
	return d

def connected_components(graph):
	seen = set()

	def dfs(v):
		vs = set([v])
		component = []
		while vs:
			v = vs.pop()
			seen.add(v)
			vs |= set(graph[v]) - seen
			component.append(v)
		return component
	ans = []
	for v in graph:
		if v not in seen:
			d = dfs(v)
			ans.append(d)
	return ans

def primeFactors(n):
	s = set()
	while n % 2 == 0:
		s.add(2)
		n = n // 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			s.add(i)
			n = n // i
	if n > 2:
		s.add(n)
	return s

def find_all(a_str, sub):
	start = 0
	while True:
		start = a_str.find(sub, start)
		if start == -1:
			return
		yield start
		start += len(sub)

def SieveOfEratosthenes(n, isPrime):
	isPrime[0] = isPrime[1] = False
	for i in range(2, n):
		isPrime[i] = True
	p = 2
	while p * p <= n:
		if isPrime[p] == True:
			i = p * p
			while i <= n:
				isPrime[i] = False
				i += p
		p += 1
	return isPrime

def dijkstra(edges, f, t):
	g = defaultdict(list)
	for (l, r, c) in edges:
		g[l].append((c, r))
	(q, seen, mins) = ([(0, f, ())], set(), {f: 0})
	while q:
		(cost, v1, path) = heappop(q)
		if v1 not in seen:
			seen.add(v1)
			path = (v1, path)
			if v1 == t:
				return (cost, path)
			for (c, v2) in g.get(v1, ()):
				if v2 in seen:
					continue
				prev = mins.get(v2, None)
				next = cost + c
				if prev is None or next < prev:
					mins[v2] = next
					heappush(q, (next, v2, path))
	return float('inf')

def binsearch(a, l, r, x):
	while l <= r:
		mid = l + (r - 1) // 2
		print(mid)
		if a[mid]:
			return mid
		elif a[mid] > x:
			l = mid - 1
		else:
			r = mid + 1
	return -1
f = 0
s = list(si())
x = tuple(s)
out = []
for i in range(len(s) + 1):
	for j in range(97, 97 + 26):
		s = list(x)
		s.insert(i, chr(j))
		out.append(''.join(s))
for i in out:
	if i == i[::-1]:
		print(i)
		f = 1
		break
if f == 0:
	print('NA')


a = input()
dead = False
semidead = False
fr = 0
ind = None
d = 0
for i in range(len(a) // 2):
	if a[i - min(fr, 0)] != a[-i - 1 - max(fr, 0)]:
		if d == 0:
			if a[i] == a[-i - 2]:
				fr = 1
				ind = i
				d += 1
			elif a[i + 1] == a[-i - 1]:
				fr = -1
				ind = len(a) - i - 1
				d += 1
			else:
				dead = True
				print('NA')
				break
		else:
			semidead = True
			break
if semidead:
	d = 0
	fr = 0
	for i in range(len(a) // 2):
		if a[i - min(fr, 0)] != a[-i - 1 - max(fr, 0)]:
			if d == 0:
				if a[i] == a[-i - 2]:
					if fr != -1:
						if a[i + 1] == a[-i - 1]:
							fr = -1
							ind = len(a) - i - 1
							d += 1
						else:
							dead = True
							print('NA')
							break
					else:
						ind = i
						d += 1
				elif a[i + 1] == a[-i - 1]:
					if fr != 1:
						dead = True
						print('NA')
						break
					ind = len(a) - i - 1
					d += 1
				else:
					dead = True
					print('NA')
					break
			else:
				dead = True
				print('NA')
				break
if not dead:
	if d == 0:
		print(a[0:len(a) // 2], a[len(a) // 2], a[len(a) // 2:], sep='')
	elif fr == 1:
		print(a[0:ind], a[-1 - ind], a[ind:], sep='')
	else:
		print(a[0:ind + 1], a[len(a) - 1 - ind], a[ind + 1:], sep='')


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 1000000007
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
s = list(input())
n = len(s)
for i in range(n + 1):
	a = s[:]
	a.insert(i, 'A')
	ok = True
	l = 0
	r = n
	while l < r:
		if a[l] == 'A':
			a[l] = a[r]
			l += 1
			r -= 1
		elif a[r] == 'A':
			a[r] = a[l]
			l += 1
			r -= 1
		elif a[l] == a[r]:
			l += 1
			r -= 1
		else:
			ok = False
			break
	if ok:
		print(''.join(a).lower())
		exit()
print('NA')


z = input()
arr = []
for i in z:
	arr.append(i)
i = 0
count = 0
while i < len(z) // 2 and count < 2:
	if arr[i] == arr[-i - 1]:
		i += 1
		continue
	else:
		count += 1
		if arr[i] == arr[-2 - i] and arr[-i - 1] == arr[i + 1]:
			arr.insert(i, arr[-i - 1])
			for k in range(len(arr) // 2):
				if arr[k] == arr[-k - 1]:
					continue
				else:
					del arr[i]
					if -1 - i == -1:
						arr.append(arr[i])
					else:
						arr.insert(-i, arr[i])
		elif arr[i] == arr[-2 - i]:
			arr.insert(i, arr[-i - 1])
		elif arr[-i - 1] == arr[i + 1]:
			if -1 - i == -1:
				arr.append(arr[i])
			else:
				arr.insert(-i, arr[i])
		else:
			count = 10
			break
		i += 1
if count == 0:
	count += 1
	arr.insert(len(arr) // 2, arr[len(arr) // 2])
for i in range(len(arr) // 2):
	if arr[i] == arr[-i - 1]:
		continue
	else:
		count = 10
if len(arr) == 1:
	arr.append(arr[0])
if count < 2:
	for i in arr:
		print(i, end='')
	print()
else:
	print('NA')


s = input()

def chk(s):
	for i in range(len(s)):
		if s[i] != s[len(s) - i - 1]:
			return False
	return True
for i in range(len(s) + 1):
	for j in range(26):
		ns = s[:i] + chr(ord('a') + j) + s[i:]
		if chk(ns):
			print(ns)
			exit(0)
print('NA')


s = input()
n = len(s)
for _ in range(n + 1):
	s1 = s[:_] + '!' + s[_:]
	s2 = s1[::-1]
	a = '?'
	for i in range(n + 1):
		if s1[i] == '!' and s2[i] != '!':
			if a == '?':
				a = s2[i]
			elif s2[i] == a:
				print(s[:_] + a + s[_:])
				exit(0)
			else:
				print('NA')
				exit(0)
		elif s1[i] != '!' and s2[i] == '!':
			if a == '?':
				a = s1[i]
			elif s1[i] == a:
				print(s[:_] + a + s[_:])
				exit(0)
			else:
				print('NA')
				exit(0)
		elif s1[i] == s2[i] == '!':
			print(s[:_] + 'a' + s[_:])
			exit(0)
		elif s1[i] != s2[i]:
			break
print('NA')


from math import ceil, floor
s = input()
l = len(s)
(h1, h2) = (ceil(l / 2), floor(l / 2))
if s[:h1] == ''.join(list(reversed(s[h2:]))):
	print(s[:h1] + s[h2] + s[h1:])
else:
	(s1, s2) = (list(s), list(s))
	for i in range(h1):
		if s[i] != s[-(i + 1)]:
			s1.insert(l - i, s[i])
			s2.insert(i, s[-(i + 1)])
			break
	l = len(s1)
	(h1, h2) = (ceil(l / 2), floor(l / 2))
	if s1[:h1] == list(reversed(s1[h2:])):
		print(''.join(s1))
	elif s2[:h1] == list(reversed(s2[h2:])):
		print(''.join(s2))
	else:
		print('NA')


import sys

def is_p(s):
	return s == s[::-1]
s = input()
for i in range(len(s) + 1):
	for c in 'abcdefghijklmnopqrstuvwxyz':
		t = s[:i] + c + s[i:]
		print(t, file=sys.stderr)
		if is_p(s[:i] + c + s[i:]):
			print(s[:i] + c + s[i:])
			exit(0)
print('NA')


letters = list('abcdefghijklmnopqrstuvwxyz')

def insertLetter(letter, word, pos):
	return word[:pos] + letter + word[pos:]

def isPalidrome(word):
	length = len(word)
	if length % 2 == 0:
		firstHalf = word[:int(length / 2)]
		secondHalf = word[length:int(length / 2) - 1:-1]
		if firstHalf == secondHalf:
			return True
		else:
			return False
	else:
		firstHalf = word[:int(length / 2)]
		secondHalf = word[length:int(length / 2):-1]
		if firstHalf == secondHalf:
			return True
		else:
			return False

def findPalidrome(word):
	for i in range(len(word) + 1):
		for letter in letters:
			newWord = insertLetter(letter, word, i)
			if isPalidrome(newWord):
				return newWord
	return 'NA'
word = input()
print(findPalidrome(word))


def pal(a):
	ctr = 0
	while ctr < len(a) / 2:
		if a[ctr] != a[len(a) - ctr - 1]:
			return False
		ctr += 1
	return True
a = input()
alp = []
p = 'NA'
if not len(a) > 10 or len(a) < 1:
	if a.islower():
		for char in a:
			if not char in alp:
				alp.append(char)
		length = len(a)
		for char in alp:
			ctr = 0
			while ctr <= length:
				new = a[:ctr] + char + a[ctr:]
				if pal(new):
					p = new
				ctr += 1
		print(p)


def palindrom(s):
	n = len(s)
	for num in range(n):
		if s[num] != s[n - num - 1]:
			return 0
	return 1
s = input()
n = len(s)
words = 'abcdefghjklmnpoqrstvwxyziuy'
yes = 0
s1 = ''
for i in range(n + 1):
	for j in words:
		if palindrom(s[:i] + j + s[i:]) == 1:
			s1 = s[:i] + j + s[i:]
			yes = 1
			break
	if yes == 1:
		break
if s1 == '':
	print('NA')
else:
	print(s1)


import math
for m in range(1, 2):
	s = input()
	s = list(s)
	half = len(s) // 2
	full = len(s)
	arr = []
	DONE = False
	string = ''

	def check():
		full = len(s)
		half = len(s) // 2
		global DONE, string
		if full % 2 == 0:
			reverse = list(s[half:full])
			reverse.reverse()
			reverse = ''.join(reverse)
			if ''.join(s[0:half]) == reverse:
				string = ''.join(s)
				DONE = True
				return
		elif full % 2 != 0:
			reverse = list(s[half + 1:full])
			reverse.reverse()
			reverse = ''.join(reverse)
			if ''.join(s[0:half]) == reverse:
				string = ''.join(s)
				DONE = True
				return
	for i in range(full):
		for j in range(full):
			if j == full - 1:
				s.insert(full, s[i])
				check()
				s.pop(full)
				if DONE == True:
					break
				continue
			s.insert(j, s[i])
			check()
			s.pop(j)
			if DONE == True:
				break
	if DONE == False:
		print('NA')
	else:
		print(string)


s = input()
if ''.join(reversed(s)) == s:
	if len(s) % 2 == 0:
		print(s[:len(s) // 2] + 'l' + s[len(s) // 2:])
	else:
		print(s[:len(s) // 2] + s[len(s) // 2] + s[len(s) // 2:])
	exit()
n = len(s)
st = s[n - 1] + s
if st == ''.join(reversed(st)):
	print(st)
	exit()
st = s + s[0]
if st == ''.join(reversed(st)):
	print(st)
	exit()
a = [0] * (n + 1)
flag = 0
i = 0
j = n - 1
f = 0
l = n
ans = 0
while i <= j:
	if s[i] == s[j]:
		a[f] = s[i]
		f += 1
		a[l] = s[j]
		l -= 1
		i += 1
		j -= 1
	elif s[i] != s[j] and flag == 0:
		a[f] = s[i]
		f += 1
		a[l] = s[i]
		l -= 1
		i += 1
		flag = 1
	elif s[i] != s[j] and flag:
		ans = 1
		break
if ans == 0:
	print(''.join((str(e) for e in a)))
else:
	for i in range(n + 1):
		a[i] = 0
	i = 0
	j = n - 1
	f = 0
	l = n
	ans = 0
	flag = 0
	while i <= j:
		if s[i] == s[j]:
			a[f] = s[i]
			f += 1
			a[l] = s[j]
			l -= 1
			i += 1
			j -= 1
		elif s[i] != s[j] and flag == 0:
			a[f] = s[j]
			f += 1
			a[l] = s[j]
			l -= 1
			j -= 1
			flag = 1
		elif s[i] != s[j] and flag:
			ans = 1
			break
	if ans:
		print('NA')
	else:
		print(''.join((str(e) for e in a)))


a = input()
for i in range(26):
	for j in range(len(a) + 1):
		b = a[:j] + chr(97 + i) + a[j:]
		if b == b[::-1]:
			print(b)
			exit()
print('NA')


def main():
	l = list(input())
	l.append(None)
	for i in range(len(l) - 1, -1, -1):
		for c in 'abcdefghijklmnopqrstuvwxyz':
			l[i] = c
			if l == l[::-1]:
				print(''.join(l))
				return
		l[i] = l[i - 1]
	print('NA')
main()


from string import ascii_lowercase

def makePalindrome(st):
	if not st or not st.isalpha() or (not st.islower()):
		return 'NA'
	for letter in ascii_lowercase:
		for pos in range(len(st) + 1):
			tmp = st[:pos] + letter + st[pos:]
			if tmp == tmp[::-1]:
				return tmp
	return 'NA'

def isPalindrome(st):
	(i, j) = (0, len(st) - 1)
	while i < j:
		if st[i] != st[j]:
			return False
		i += 1
		j -= 1
	return True
st = input()
print(makePalindrome(st))


def main():
	la = list(input())
	la.append('a')
	lb = la[::-1]
	j = len(la) - 1
	for i in range(len(lb)):
		for c in 'abcdefghijklmnopqrstuvwxyz':
			la[j] = lb[i] = c
			if la == lb:
				print(''.join(la))
				return
		la[j] = lb[i] = la[j - 1]
		j -= 1
	print('NA')
main()


s = [x for x in input()]
for i in range(len(s) + 1):
	for j in range(ord('a'), ord('z') + 1):
		t = s[:]
		t.insert(i, chr(j))
		(l, k) = (0, len(t) - 1)
		while l < k:
			if t[l] == t[k]:
				l += 1
				k -= 1
			else:
				break
		else:
			print(''.join(t))
			exit(0)
print('NA')


s = input()
if s == s[::-1]:
	print(s[:len(s) // 2] + s[len(s) // 2] + s[len(s) // 2:])
elif s[0] != s[-1]:
	s1 = s[:-1] + s[-1] + s[0]
	s2 = s[-1] + s
	if s1 == s1[::-1]:
		print(s1)
	elif s2 == s2[::-1]:
		print(s2)
	else:
		print('NA')
else:
	for i in range(1, len(s) // 2):
		if s[i] != s[len(s) - i - 1]:
			s1 = s[:len(s) - i - 1] + s[len(s) - i - 1] + s[i] + s[-i:]
			s2 = s[:i] + s[-i - 1] + s[i:]
			break
	if s1 == s1[::-1]:
		print(s1)
	elif s2 == s2[::-1]:
		print(s2)
	else:
		print('NA')


from string import ascii_lowercase
import sys

def is_palindrome(x):
	return x == x[::-1]
s = [c for c in input()]
for c in ascii_lowercase:
	for i in range(len(s) + 1):
		new_s = s[:i] + [c] + s[i:]
		if is_palindrome(new_s):
			print(''.join(new_s))
			sys.exit(0)
print('NA')


st1 = input()
a = len(st1) + 1
for i in range(26):
	for j in range(a):
		st2 = st1[:j] + chr(i + 97) + st1[j:]
		if st2 == st2[::-1]:
			print(st2)
			exit()
print('NA')


s = input()
f = 0
alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for i in range(len(s) + 1):
	for j in alpha:
		t = s[:i] + j + s[i:]
		if t == t[::-1]:
			print(t)
			exit()
print('NA')


def f(s):
	at = -1
	for (i, v) in enumerate(s):
		if v == '@':
			at = i
			continue
		if v != s[-i - 1] and s[-i - 1] != '@':
			return False
	s[at] = s[-at - 1]
	return ''.join(s)
s = list(input())
for i in range(len(s) + 1):
	s.insert(i, '@')
	a = f(s)
	if a:
		print(a)
		break
	del s[i]
else:
	print('NA')


x = input()
d = False
for c in range(97, 123):
	if d:
		break
	for i in range(len(x) + 1):
		n = x[:i] + chr(c) + x[i:]
		if n == n[::-1]:
			print(n)
			d = True
			break
if not d:
	print('NA')


from string import ascii_lowercase
word = str(input())
found = False

def get_palindrome(word, len):
	global found
	for letter in ascii_lowercase:
		new_word = word[:x] + letter + word[x:]
		if new_word[::-1] == new_word:
			print(new_word)
			found = True
			return
for x in range(len(word) + 1):
	if not found:
		get_palindrome(word, x)
if not found:
	print('NA')


def main():
	s = input()
	for i in range(len(s) + 1):
		for sym in range(ord('a'), ord('z') + 1):
			sym = chr(sym)
			st = s[:i] + sym + s[i:]
			if st == st[::-1]:
				print(st)
				return
	print('NA')
main()


from sys import *
import math
input = stdin.readline
I = int
R = range
listInput = lambda : list(map(int, input().strip().split()))
lineInput = lambda : map(int, input().strip().split())
sJoin = lambda a, sep: '{}'.format(sep).join(a)
arrJoin = lambda a, sep: '{}'.format(sep).join(map(str, a))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(math.sqrt(n) + 1), 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def main():
	s = input().strip()
	(i, j) = (0, len(s) - 1)
	pos = 0
	char = ''
	jchar = ''
	ipos = 0
	while i < j:
		if s[i] != s[j]:
			pos = j
			ipos = i
			char = s[i]
			jchar = s[j]
			break
		i += 1
		j -= 1
	if pos == 0:
		L = len(s)
		mid = (L + 2 - 1) // 2
		(first, last) = (s[:mid], s[mid:])
		s = first + s[mid - 1] + last
		print(s)
	else:
		(first, last) = (s[:pos + 1], s[pos + 1:])
		(start, stop) = (s[:ipos], s[ipos:])
		r = start + jchar + stop
		s = first + char + last
		if s[:] == s[::-1]:
			print(s)
		elif r[:] == r[::-1]:
			print(r)
		else:
			print('NA')
main()


a = []
for i in range(97, 123):
	a.append(chr(i))
s = input()
n = len(s)
flag = False
for i in range(n + 1):
	if flag == False:
		for j in a:
			x = s[0:i] + j + s[i:n]
			if x == x[::-1]:
				y = x
				flag = True
				break
if flag == False:
	print('NA')
else:
	print(y)


__author__ = 'artyom'

def main():
	s = list(read(0))
	n = len(s)
	m = n // 2
	for i in range(n + 1):
		p = s[:i] + [s[n - i - (i <= m)]] + s[i:n]
		if p == p[::-1]:
			return p
	return 'NA'

def read(mode=2):
	inputs = input().strip()
	if mode == 0:
		return inputs
	if mode == 1:
		return inputs.split()
	if mode == 2:
		return int(inputs)
	if mode == 3:
		return list(map(int, inputs.split()))

def write(s='\n'):
	if s is None:
		s = ''
	if isinstance(s, list):
		s = ''.join(map(str, s))
	s = str(s)
	print(s, end='')
write(main())


import string
s = input()
done = False
for i in range(len(s) + 1):
	for a in string.ascii_lowercase:
		ns = s[:i] + a + s[i:]
		if ns == ns[::-1]:
			print(ns)
			done = True
			break
	if done:
		break
if not done:
	print('NA')


def main():
	s = input()
	for i in range(len(s)):
		t = s[:i] + s[i + 1:]
		if t == t[::-1]:
			if i <= len(s) // 2:
				print(s[:len(s) - i] + s[i] + s[len(s) - i:])
			else:
				print(s[:len(s) - i - 1] + s[i] + s[len(s) - i - 1:])
			return
	print('NA')
	return
main()


from string import ascii_lowercase
ans = None
string = input()
for ch in ascii_lowercase:
	for i in range(len(string) + 1):
		s = string[:i] + ch + string[i:]
		if s == s[::-1]:
			ans = s
if ans:
	print(ans)
else:
	print('NA')


TN = 1

def solution():
	s = list(input())
	n = len(s)
	ans = []
	for i in range(n):
		ans.append(s[:i] + [s[-i - 1]] + s[i:])
		ans.append(s[:i + 1] + [s[-i - 1]] + s[i + 1:])
	for i in range(len(ans)):
		for j in range(len(ans[i]) // 2 + 1):
			if ans[i][j] != ans[i][-j - 1]:
				break
		else:
			print(''.join(ans[i]))
			break
	else:
		print('NA')
while TN != 0:
	solution()
	TN -= 1


import string

def jud(l=[]):
	n = len(l)
	for i in range(n):
		if l[i] != l[n - i - 1]:
			return False
	return True
s = input('')
n = len(s)
arr = list(s)
flag = False
for i in range(n + 1):
	if flag:
		break
	for c in string.ascii_lowercase:
		if flag:
			break
		arr.insert(i, c)
		if jud(arr):
			print(''.join(arr))
			flag = True
		arr.pop(i)
if not flag:
	print('NA')


s = input()
for i in range(len(s) + 1):
	for j in range(97, 123):
		a = chr(j)
		t = s[:i] + a + s[i:]
		if t == t[::-1]:
			print(t)
			exit()
print('NA')


import sys
s = input()
if s + s[0] == s[0] + s[::-1]:
	print(s + s[0])
	sys.exit()
for x in s:
	for y in range(len(s)):
		b = list(s)
		b.insert(y, x)
		if b == b[::-1]:
			print(''.join(b))
			sys.exit()
print('NA')


def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def MAP2():
	return map(float, input().split())

def LIST():
	return list(map(int, input().split()))

def STRING():
	return input()
import string
from heapq import heappop, heappush
from bisect import *
from collections import deque, Counter
from math import *
from itertools import permutations, accumulate
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def check(s):
	if s == s[::-1]:
		return True
	return False
s = STR()
ans = ''
flag = False
st_letters = set(s)
for i in range(11):
	for j in st_letters:
		z = s.copy()
		z.insert(i, j)
		if check(z):
			flag = True
			ans = ''.join(z)
			break
if flag:
	print(ans)
else:
	print('NA')


def palindrome(s):
	if list(s) == list(reversed(list(s))):
		return 1
	return 0
s = input()
done = 0
for i in range(0, len(s) + 1):
	for j in range(97, 123):
		l = s[:i] + chr(j) + s[i:]
		if palindrome(l) == 1 and done == 0:
			print(l)
			done = 1
if done == 0:
	print('NA')


import string

def main():
	s = input()
	for i in range(len(s) + 1):
		for a in string.ascii_lowercase:
			ns = s[:i] + a + s[i:]
			if ns == ns[::-1]:
				print(ns)
				return
	print('NA')
main()


s = list(input())
length = len(s)
i = 0
j = length - 1
while i < j:
	if s[i] == s[j]:
		i += 1
		j -= 1
	else:
		a = s[:j + 1] + [s[i]] + s[j + 1:]
		b = s[:i] + [s[j]] + s[i:]
		break
else:
	if len(s) % 2 == 0:
		print(''.join(s[:length // 2] + ['a'] + s[length // 2:]))
	else:
		print(''.join(s[:length // 2] + [s[length // 2]] + s[length // 2:]))
	exit()
c = a[::-1]
d = b[::-1]
if a == c:
	print(''.join(a))
elif b == d:
	print(''.join(b))
else:
	print('NA')


(s, x) = (list(input()), 0)
a = s[:]
for i in range(len(s)):
	if s[i] != s[len(s) - 1 - i]:
		x = 1
		a.insert(i, s[len(s) - 1 - i])
		s.insert(len(s) - i, s[i])
		break
if x:
	x = 0
	for i in range(len(s)):
		if s[i] != s[len(s) - i - 1]:
			x = 1
			break
	if x:
		x = 0
		for i in range(len(a)):
			if a[i] != a[len(a) - i - 1]:
				x = 1
				break
		if x:
			print('NA')
		else:
			print(''.join(a))
	else:
		print(''.join(s))
else:
	s.insert(int(len(s) / 2), s[int(len(s) / 2)])
	print(''.join(s))


s = input()
n = len(s)

def symi(i, k):
	if min(k, n - k - 1) < min(i, n - i - 1):
		return n - k - 1
	elif min(k, n - k - 1) > min(i, n - i - 1) and i > n // 2:
		return n - k
	elif min(k, n - k - 1) > min(i, n - i - 1):
		return n - k - 2
	else:
		return k

def ispal(s, i):
	b = True
	for k in range(n):
		if s[symi(i, k)] != s[k]:
			b = False
	return b

def res(s):
	for i in range(n):
		if ispal(s, i):
			if i > n // 2:
				sp = s[:i + 1] + s[n - i - 1] + s[i + 1:]
			else:
				sp = s[:i] + s[n - i - 1] + s[i:]
			return sp
	return 'NA'
print(res(s))


abc = 'abcdefghijklmnopqrstuvwxyz'

def is_palindrome(s):
	if s == s[::-1]:
		return True
	else:
		return False
s = input()
for i in range(len(s) + 1):
	for t in abc:
		s2 = s[:i] + t + s[i:]
		if is_palindrome(s2):
			print(s2)
			exit(0)
print('NA')


s = input()
if s == s[::-1]:
	print(s[:len(s) // 2] + s[len(s) // 2] + s[len(s) // 2:])
else:
	for i in range(len(s) // 2):
		if s[i] != s[len(s) - 1 - i]:
			first = s[:i] + s[len(s) - 1 - i] + s[i:]
			second = s[:len(s) - i] + s[i] + s[len(s) - i:]
			if first == first[::-1]:
				print(first)
			elif second == second[::-1]:
				print(second)
			else:
				print('NA')
			break


st = list(input())
for i in range(len(st) + 1):
	for j in range(26):
		sti = st.copy()
		sti.insert(i, chr(97 + j))
		if sti == sti[::-1]:
			print(''.join(sti))
			exit()
print('NA')


inStr = input()

def isPal(s):
	return s == s[::-1]

def insertCharAt(s, c, i):
	return s[:i] + c + s[i:]

def getAnswer():
	for c in 'abcdefghijklmnopqrstuvwxyz':
		for i in range(len(inStr) + 1):
			newStr = insertCharAt(inStr, c, i)
			if isPal(newStr):
				return newStr
	return 'NA'
ans = getAnswer()
print(ans)


s = input()
for i in range(len(s) + 1):
	for j in 'abcdefghijklmnopqrstuvwxyz':
		t = s[:i] + j + s[i:]
		if t == t[::-1]:
			print(t)
			exit()
print('NA')


s = input()

def palin(p):
	w = 0
	if len(p) == 1:
		return True
	else:
		for i in range(len(p) // 2):
			if p[i] != p[-1 - i]:
				w = 2
				break
			else:
				w = 0
		if w == 0:
			return True
		else:
			return False

def same(e):
	t = e[0]
	r = 1
	for i in range(1, len(e)):
		if e[i] != t:
			r = 2
			break
	if r == 2:
		return False
	else:
		return True
if same(s) != True:
	if len(s) == 1:
		t = s + s
		print(t)
	elif palin(s) == True:
		if len(s) % 2 == 0:
			r = len(s) // 2
			w = s[0:r] + 'a' + s[r:len(s)]
			print(w)
		else:
			s = s[0:len(s) // 2 + 1] + s[len(s) // 2] + s[len(s) // 2 + 1:]
			print(s)
	else:
		for i in range(len(s)):
			if s[i] != s[-1 - i]:
				m = s[-1 - i] + s[i:len(s) - i]
				n = s[i:len(s) - i] + s[i]
				if palin(m) == True:
					d = s[0:i] + m + s[len(s) - i:]
					print(d)
					break
				elif palin(n) == True:
					d = s[0:i] + n + s[len(s) - i:]
					print(d)
					break
				else:
					print('NA')
					break
else:
	s = s + s[0]
	print(s)


s = list(input())
p = s.copy()
o = 1
for i in range(0, len(s)):
	s = p.copy()
	s.insert(len(s) - i, s[i])
	if s == s[::-1]:
		for l in s:
			print(l, end='')
		o = 0
		break
if o:
	p = p[::-1]
	s = p.copy()
	for i in range(0, len(s)):
		s = p.copy()
		s.insert(len(s) - i, s[i])
		if s == s[::-1]:
			for l in s:
				print(l, end='')
			o = 0
			break
if o:
	print('NA')


def ispal(s):
	i = 0
	j = len(s) - 1
	while i < j:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True
alpha = 'abcdefghijklmnopqrstuvwxyz'
found = 0
s = input()
for i in range(0, len(s) + 1):
	for j in range(len(alpha)):
		temp = s[:i] + alpha[j] + s[i:]
		if ispal(temp):
			found = 1
			print(temp)
			break
	if found:
		break
if not found:
	print('NA')


def func(s):
	for i in range(len(s) + 1):
		for j in range(97, 123):
			q = s[:i] + chr(j) + s[i:]
			rev = q[::-1]
			if q == rev:
				return q
	return 'NA'
s = input()
print(func(s))


s = input()
al = 'abcdefghijklmnopqrstuvwxyz'
ans = False
for i in range(26):
	for j in range(len(s) + 1):
		tmp = s[:j] + al[i] + s[j:]
		if tmp == tmp[::-1]:
			print(tmp)
			exit()
print('NA')


def check(word):
	newWord = list(word)
	l = len(word) - 1
	i = 0
	while l != -1:
		newWord[i] = word[l]
		i += 1
		l -= 1
	if word == newWord:
		return True
	return False

def Main():
	s = input()
	leng = len(s)
	symbol = leng - 1
	s = list(s)
	newS = s.copy()
	insertPos = 0
	for char in s:
		if symbol == insertPos:
			newS.insert(insertPos, 'a')
			if check(newS.copy()):
				print(''.join(newS))
				return
		else:
			newS.insert(insertPos, s[symbol])
			if check(newS.copy()):
				print(''.join(newS))
				return
		newS = s.copy()
		symbol -= 1
		insertPos += 1
	symbol = 0
	insertPos = leng
	newS = s.copy()
	for char in s:
		if symbol == insertPos:
			newS.insert(insertPos, 'a')
			if check(newS.copy()):
				print(''.join(newS))
				return
		else:
			newS.insert(insertPos, s[symbol])
			if check(newS.copy()):
				print(''.join(newS))
				return
		newS = s.copy()
		symbol += 1
		insertPos -= 1
	newS = s.copy()
	newS.append(s[0])
	if check(newS):
		print(''.join(newS))
		return
	print('NA')
Main()


alph = list('abcdefghijklmnopqrstuvwxyz')

def pal(s):
	l = len(s)
	f = 1
	lim = l / 2
	l -= 1
	for i in range(int(lim)):
		if s[i] != s[l - i]:
			f = 0
	return f
s = input()
l = len(s) + 1
f = 0
for i in range(l):
	for j in alph:
		st = list(s)
		st.insert(i, j)
		st = ''.join(st)
		if pal(st) == 1:
			f = 1
			break
	if f == 1:
		break
if f == 1:
	print(st)
else:
	print('NA')