Mr. Kitayuta has kindly given you a string s consisting of lowercase English letters. You are asked to insert exactly n lowercase English letters 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 n lowercase English letters, and insert each of them to any position of s, possibly to the beginning or the end of s. You have to insert exactly n letters even if it is possible to turn s into a palindrome by inserting less than n letters.

Find the number of the palindromes that can be obtained in this way, modulo 10007.

Input

The first line contains a string s (1 ≤ |s| ≤ 200). Each character in s is a lowercase English letter.

The second line contains an integer n (1 ≤ n ≤ 109).

Output

Print the number of the palindromes that can be obtained, modulo 10007.

Examples

Input

revive
1


Output

1


Input

add
2


Output

28

Note

For the first sample, you can obtain the palindrome "reviver" by inserting 'r' to the end of "revive".

For the second sample, the following 28 palindromes can be obtained: "adada", "adbda", ..., "adzda", "dadad" and "ddadd".

Difficulty: VERY_HARD
Tags: Matrices

Combinatorics

Dynamic programming

String algorithms
Skill types: Dynamic programming

Starter code:

Solutions:
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')


import sys
s = sys.stdin.readline().strip()

def getPalindrom(s):
	a = ord('a')
	for i in range(len(s) + 1):
		for char in range(26):
			new_s = s[:i] + chr(a + char) + s[i:]
			left = new_s[:len(new_s) // 2]
			right = new_s[len(new_s) // 2 + len(new_s) % 2:][::-1]
			if left == right:
				return new_s
	return 'NA'

def doTest():
	assert getPalindrom('revive') == 'reviver'
	assert getPalindrom('kitayuta') == 'NA'
print(getPalindrom(s))


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


s = input()
n = len(s)
con = 0
for x in range(n + 1):
	for y in range(97, 97 + 26):
		k = s[:x] + chr(y) + s[x:]
		if k == k[::-1]:
			print(k)
			con = 1
			break
	if con:
		break
else:
	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')


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')


string = list(input())
for i in range(len(string)):
	cur = ord('a')
	for let in range(26):
		ins = chr(cur + let)
		string.insert(i, ins)
		if string == string[::-1]:
			print(''.join(string))
			exit()
		del string[i]
else:
	for let in range(26):
		ins = chr(cur + let)
		string.append(ins)
		if string == string[::-1]:
			print(''.join(string))
			exit()
		del string[len(string) - 1]
	print('NA')


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')


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


word = input().strip()

def testPalindrome(word):
	length = len(word)
	for x in range(int(length / 2)):
		if word[x] != word[length - 1 - x]:
			return False
	return True

def reverseString(word):
	return word[::-1]

def findIndex(word1, word2):
	length = len(word1)
	for i in range(length):
		if word1[i] != word2[i]:
			return i
	return -1

def findDiffIndex(word):
	newString = ''
	if len(word) % 2 == 0:
		(first, second) = (word[:int(len(word) / 2)], word[int(len(word) / 2):][::-1])
		a = findIndex(first, second)
		if a == -1:
			newString = first + 'x' + second[::-1]
			print(newString)
		else:
			newString = first[:a] + second[a] + first[a:] + second[::-1]
			if testPalindrome(newString):
				print(newString)
			else:
				newString = first + second[a:][::-1] + first[a] + second[:a][::-1]
				if testPalindrome(newString):
					print(newString)
				else:
					print('NA')
	else:
		(first, second) = (word[:int(len(word) / 2)], word[int(len(word) / 2) + 1:][::-1])
		a = findIndex(first, second)
		midChar = word[int(len(word) / 2)]
		if a == -1:
			newString = first + midChar + midChar + second[::-1]
			print(newString)
		else:
			newString = first[:a] + second[a] + first[a:] + midChar + second[::-1]
			if testPalindrome(newString):
				print(newString)
			else:
				newString = first + midChar + second[a:][::-1] + first[a] + second[:a][::-1]
				if testPalindrome(newString):
					print(newString)
				else:
					print('NA')
findDiffIndex(word)


def is_pal(s):
	for i in range(len(s) >> 1):
		if s[i] != s[len(s) - i - 1]:
			return False
	return True

def main():
	s = input()
	for offset in range(26):
		for i in range(len(s) + 1):
			s2 = s[:i] + chr(ord('a') + offset) + s[i:]
			if is_pal(s2):
				print(s2)
				return
	print('NA')
main()


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()


s = str(input())
s = list(s)
s1 = s[::-1]
answer = ''
output = s
if len(s) == 1:
	s += s
	output = list(s)
elif s == s1:
	for element in s:
		s.insert(int(len(s) / 2), element)
		if s == s[::-1]:
			break
		else:
			s.pop(int(len(s) / 2) - 1)
	output = s
else:
	for letter in s:
		count = 0
		while count <= len(s):
			s.insert(count, letter)
			s1 = s[::-1]
			if s1 == s:
				output = s1
			s.pop(count)
			count += 1
if output == output[::-1]:
	for letter in output:
		answer += letter
	print(answer)
else:
	print('NA')


s = input()
l = len(s)
for i in range(l + 1):
	cur = s[:i] + s[l - i - 1 + (i > l // 2)] + s[i:]
	if all((cur[i] == cur[l - i] for i in range((l + 1) // 2))):
		(print(cur), exit())
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')


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)


def ispal(s):
	for i in range(len(s)):
		if s[i] != s[len(s) - i - 1]:
			return False
	return True
s = input()
for i in range(len(s) + 1):
	if i <= len(s) // 2:
		t = s[:i] + s[len(s) - 1 - i] + s[i:]
	else:
		t = s[:i] + s[len(s) - i] + s[i:]
	if ispal(t):
		print(t)
		import sys
		sys.exit()
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')


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')


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()


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 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)


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')


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')


import sys
import string
a = input()
lens = len(a)
flag = 0
lis = list()
for i in range(0, lens):
	lis.append(a[i])
for i in range(0, lens + 1):
	for word in string.ascii_lowercase:
		s = lis[:]
		s.insert(i, word)
		q = ''
		q = ''.join(s)
		p = q[::-1]
		if p == q:
			flag = 1
			print(p)
			break
	if flag == 1:
		break
if flag == 0:
	print('NA\n')


import sys

def checkRest(word):
	left = 0
	right = len(word) - 2
	while left <= right:
		if word[left] != word[right]:
			return False
		left += 1
		right -= 1
	return True

def palen(line):
	left = 0
	right = len(line) - 2
	while left < right:
		if line[left] != line[right]:
			worda = line[:right + 1] + line[left] + line[right + 1:]
			wordb = line[:left] + line[right] + line[left:]
			if checkRest(worda):
				print(worda)
				return
			elif checkRest(wordb):
				print(wordb)
				return
			else:
				print('NA')
				return
		left += 1
		right -= 1
	print(line[:right] + line[right] + line[right:])
	return

def main():
	for line in sys.stdin:
		palen(line)
main()


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')


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


__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())


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')


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')


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')


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 = input()
n = len(s)
ok = False
for i in range(len(s) + 1):
	for j in range(97, 123):
		q = s[:i] + chr(j) + s[i:]
		if q == q[::-1]:
			ok = True
			print(q)
			break
	if ok:
		break
if not ok:
	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')


s = input()
i = 0

def checkpa(st):
	if st == st[::-1]:
		return 1
	else:
		return 0
while i <= len(s) - 1 and s[i] == s[len(s) - 1 - i]:
	i += 1
if i == len(s):
	if len(s) % 2 == 0:
		print(s[:len(s) // 2] + 'a' + s[len(s) // 2:])
	else:
		print(s[:len(s) // 2] + s[len(s) // 2] * 2 + s[len(s) // 2 + 1:])
elif i == 0:
	s1 = s[len(s) - 1] + s
	s2 = s + s[0]
	if checkpa(s1) == 1:
		print(s1)
	elif checkpa(s2) == 1:
		print(s2)
	else:
		print('NA')
else:
	s1 = s[:i] + s[len(s) - 1 - i] + s[i:]
	s2 = s[:len(s) - i] + s[i] + s[len(s) - i:]
	if checkpa(s1) == 1:
		print(s1)
	elif checkpa(s2) == 1:
		print(s2)
	else:
		print('NA')


def solve(w):
	if w == ''.join(reversed(w)):
		return w[:len(w) // 2] + w[len(w) // 2] + w[len(w) // 2:]
	(i, j, c) = (0, len(w) - 1, -1)
	while i < j:
		if w[i] != w[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 w[:c + 1] + w[len(w) - 1 - c] + w[c + 1:]
	(i, j, c) = (0, len(w) - 1, -1)
	while i < j:
		if w[i] != w[j]:
			if c != -1:
				(i, j, c) = (-1, -1, -1)
				break
			else:
				c = i
				j -= 1
		else:
			i += 1
			j -= 1
	if c != -1:
		return w[:c] + w[len(w) - 1 - c] + w[c:]
	return 'NA'
print(solve(input()))


import sys
s = input()
for x in 'qwertyuiopasdfghjklzxcvbnm':
	for i in range(len(s) + 1):
		y = s[:i] + x + s[i:]
		if y == y[::-1]:
			print(y)
			sys.exit(0)
print('NA')


s = input()

def isPalindrome(l):
	if len(l) == 0 or len(l) == 1:
		return True
	if l[0] != l[-1]:
		return False
	else:
		return isPalindrome(l[1:len(l) - 1])
for i in range(len(s) + 1):
	for j in range(26):
		x = s[0:i] + str(chr(97 + j)) + s[i:]
		if isPalindrome(x):
			print(x)
			quit()
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 check(s):
	for i in range(len(s)):
		if s[i] != s[len(s) - i - 1]:
			return False
	return True
s = input()
for i in range(len(s) + 1):
	for c in range(ord('a'), ord('z') + 1):
		ss = s[:i] + chr(c) + s[i:]
		if check(ss):
			print(ss)
			exit(0)
print('NA')


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')


def solve(s):
	for i in range(len(s) + 1):
		for j in range(26):
			sn = s[:i] + chr(j + 97) + s[i:]
			if len(sn) & 1 == 0:
				if sn[:len(sn) // 2] == sn[len(sn) // 2:][::-1]:
					return sn
			elif sn[:len(sn) // 2] == sn[1 + len(sn) // 2:][::-1]:
				return sn
	return 'NA'
s = input()
print(solve(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))


import sys
import math
import itertools
import functools
import collections
import operator
import fileinput
import copy
ORDA = 97

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

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

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

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	newnumber = 0
	while number > 0:
		newnumber += number % base
		number //= base
	return newnumber

def cdiv(n, k):
	return n // k + (n % k != 0)

def ispal(s):
	for i in range(len(s) // 2 + 1):
		if s[i] != s[-i - 1]:
			return False
	return True
s = input()
for i in range(len(s) + 1):
	for j in range(26):
		ls = list(s)
		ls.insert(i, chr(ORDA + j))
		if ispal(ls):
			print(''.join(ls))
			exit()
else:
	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))


s = input()
for c in s:
	for i in range(len(s) + 1):
		f = s[:i] + c + s[i:]
		if f == f[::-1]:
			print(f)
			exit()
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')


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()
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, 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))


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 palindrome(s):
	n = len(s)
	for i in range(n // 2):
		if s[i] != s[n - 1 - i]:
			return False
	return True
s = input()
n = len(s)
for i in range(n + 1):
	for j in range(26):
		c = chr(ord('a') + j)
		tmp = ''
		if i > 0:
			tmp = s[0:i]
		tmp += str(c)
		if i <= n - 1:
			tmp += s[i:]
		if palindrome(tmp):
			print(tmp)
			exit()
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()


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()


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)))


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')


import sys

def checkRest(word):
	left = 0
	right = len(word) - 1
	while left <= right:
		if word[left] != word[right]:
			return False
		left += 1
		right -= 1
	return True

def palen(line):
	left = 0
	right = len(line) - 1
	while left < right:
		if line[left] != line[right]:
			worda = line[:right + 1] + line[left] + line[right + 1:]
			wordb = line[:left] + line[right] + line[left:]
			if checkRest(worda):
				print(worda)
				return
			elif checkRest(wordb):
				print(wordb)
				return
			else:
				print('NA')
				return
		left += 1
		right -= 1
	print(line[:right] + line[right] + line[right:])
	return

def main():
	palen(input())
main()


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')


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)


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 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 = 1
i = 0
while i < len(s):
	j = 0
	x = s[i]
	while j <= len(s):
		s.insert(j, x)
		if check(s):
			ans = ''.join(s)
		s.pop(j)
		j += 1
	if ans != 1:
		break
	i += 1
if ans != 1:
	print(ans)
else:
	print('NA')


s = input()
l = len(s)
x = ''
flag = 0
for i in range(0, l + 1):
	for j in range(97, 123):
		z = s[0:i] + chr(j) + s[i:]
		y = z[::-1]
		if z == y:
			flag = 1
			break
	if flag == 1:
		break
if flag == 1:
	print(z)
else:
	print('NA')


s = input()
n = len(s)
f = False
for i in range(len(s) // 2):
	if s[i] != s[n - 1 - i]:
		o = s[:n - i] + s[i] + s[n - i:]
		p = s[:i] + s[n - i - 1] + s[i:]
		f = True
		if o == o[::-1]:
			print(o)
		elif p == p[::-1]:
			print(p)
		else:
			print('NA')
		break
if not f:
	if n % 2 == 0:
		print(s[:n // 2] + 'y' + s[n // 2:])
	else:
		x = s[n // 2]
		print(s[:n // 2] + x + s[n // 2:])


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)


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 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))


from string import ascii_lowercase
from sys import stdin

def is_palindrome(s):
	return s == s[::-1]
for s in stdin:
	s = s[:-1]
	r = range(len(s) + 1)
	b = False
	for i in r:
		for c in ascii_lowercase:
			t = s[:i] + c + s[i:]
			if is_palindrome(t):
				print(''.join(t))
				b = True
				break
		if b:
			break
	else:
		print('NA')


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')


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()
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


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')


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)


alphabet = ['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']
s = input()
a = len(s)
condition = False
for x in range(a + 1):
	for y in alphabet:
		temp = s[:x] + y + s[x:]
		if temp[::-1] == temp:
			condition = True
			print(temp)
			break
	if condition:
		break
else:
	print('NA')


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')


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')


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')


from string import ascii_lowercase

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

def main():
	s = input()
	for i in range(len(s) + 1):
		for c in ascii_lowercase:
			t = s[:i] + c + s[i:]
			if is_palindrome(t):
				print(t)
				return
	print('NA')
main()


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')


def make_palindrome(s):
	if len(s) == 0:
		return 'a'
	if len(s) == 1:
		return s + s
	(i, j) = (0, len(s) - 1)
	s = list(s)
	new_wrd = None
	while i < j:
		if s[i] != s[j]:
			new_wrd = True
			break
		i += 1
		j -= 1
	if new_wrd is not None:
		new_wrd = s[:j + 1] + [s[i]] + s[j + 1:]
		if ''.join(new_wrd) == ''.join(new_wrd)[::-1]:
			return ''.join(new_wrd)
		else:
			new_wrd = s[:i] + [s[j]] + s[i:]
			if ''.join(new_wrd) == ''.join(new_wrd)[::-1]:
				return ''.join(new_wrd)
			return 'NA'
	else:
		if i == j:
			new_wrd = s[:i + 1] + [s[j]] + s[j + 1:]
		else:
			new_wrd = s[:j + 1] + ['a'] + s[i:]
		return ''.join(new_wrd)
s = input()
print(make_palindrome(s))


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')


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)


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)


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')


from string import ascii_lowercase

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

def main():
	s = input()
	for i in range(len(s) + 1):
		j = -i - (1 if i <= len(s) / 2 else 0)
		t = s[:i] + s[j] + s[i:]
		if is_palindrome(t):
			print(t)
			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')


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')


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')


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()


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)


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 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
from sys import stdin

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

def test_case(s):
	for i in range(len(s) + 1):
		j = -i - (1 if i <= len(s) / 2 else 0)
		c = s[j]
		t = s[:i] + c + s[i:]
		if is_palindrome(t):
			print(t)
			return
	print('NA')

def main():
	for s in stdin:
		test_case(s[:-1])
main()


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')


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')


from functools import reduce
from operator import *
from math import *
from sys import *
from string import *
setrecursionlimit(10 ** 7)
RI = lambda : list(map(int, input().split()))
RS = lambda : input().rstrip().split()

def isPalindrome(a):
	return a == a[::-1]
x = RS()[0]
for i in range(len(x) + 1):
	(a, b) = (x[:i], x[i:])
	for c in ascii_lowercase:
		if isPalindrome(a + c + b):
			print(a + c + b)
			exit(0)
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')


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')


def isPalindrome(g):
	flag = 0
	[p, q] = [0, len(g) - 1]
	while p < q:
		if g[p] != g[q]:
			flag = 1
			break
		p += 1
		q -= 1
	if flag == 1:
		return 0
	else:
		return 1

def main():
	mode = 'filee'
	if mode == 'file':
		f = open('test.txt', 'r')
	gets = lambda : [str(x) for x in (f.readline() if mode == 'file' else input()).split()]
	[g] = gets()
	h = list(set(list(g)))
	for i in range(len(g) + 1):
		for j in h:
			if isPalindrome(g[0:i] + j + g[i:]):
				print(g[0:i] + j + g[i:])
				return
	print('NA')
	if mode == 'file':
		f.close()
main()


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):])


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


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='')


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 pal(s):
	l = 0
	r = len(s) - 1
	while l < r:
		if s[l] != s[r]:
			return False
		l += 1
		r -= 1
	return True
s = input()
l = 0
r = len(s) - 1
f = True
while l < r:
	if s[l] != s[r]:
		s1 = s[:l] + s[r] + s[l:]
		s2 = s[:r + 1] + s[l] + s[r + 1:]
		f = False
		break
	l += 1
	r -= 1
if f:
	p = len(s) // 2
	s1 = s[:p] + s[p] + s[p:]
	s2 = s1
if pal(s1):
	print(s1)
elif pal(s2):
	print(s2)
else:
	print('NA')


def palindrome(s, insert):

	def check_ends(s):
		return s[0] == s[-1]
	if len(s) == 0:
		return 'a' if insert else s
	elif len(s) == 1:
		return s + s if insert else s
	if check_ends(s):
		p = palindrome(s[1:-1], insert)
		if p is not None:
			return s[0] + p + s[-1]
		else:
			return None
	elif insert:
		if palindrome(s[1:], False):
			return s + s[0]
		elif palindrome(s[:-1], False):
			return s[-1] + s
		else:
			return None
	else:
		return None
s = input()
p = palindrome(s, True)
print(p if p else 'NA')


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='')


from sys import stdin, stdout
from itertools import permutations as perms

def is_palindrome(line):
	for i in range(0, len(line)):
		if line[i] != line[len(line) - i - 1]:
			return False
	return True

def main():
	line = stdin.readline().rstrip()
	for i in range(0, len(line) + 1):
		for each in map(chr, range(ord('a'), ord('z') + 1)):
			my_str = line[0:i] + each + line[i:]
			if is_palindrome(my_str):
				print(my_str)
				return
	print('NA')
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')


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')


import string

def func(s):
	abc = string.ascii_lowercase
	len1 = len(s)
	for i in range(len1 + 1):
		av = (len1 + 1) // 2
		for j in range(26):
			s1 = s[:i] + abc[j] + s[i:]
			if (len1 + 1) % 2 == 0:
				if s1[:av] == ''.join(reversed(s1[av:])):
					return s1
			elif s1[:av] == ''.join(reversed(s1[av + 1:])):
				return s1
	return 'NA'
print(func(input()))


s = input()
l = (len(s) + 1) // 2
k = 'qwertyuiopasdfghjklzxcvbnm'
ans = 'NA'
for i in range(len(s) + 1):
	for j in k:
		e = ''
		b = s
		b = s[:i] + j + s[i:]
		r = [x for x in b[-l:]]
		r.reverse()
		for c in r:
			e = e + c
		if b[:l] == e:
			ans = b
print(ans)


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')


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()
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')


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')


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 sys import stdin, stdout

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

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

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

def si():
	return stdin.readline()

def ispal(s):
	n = len(s) // 2
	if s[:n] == s[-n:][::-1]:
		return True
	else:
		return False
s1 = input()
for i in range(len(s1) + 1):
	for j in range(ord('a'), ord('z') + 1):
		s2 = s1[:i] + chr(j) + s1[i:]
		if ispal(s2):
			print(s2)
			exit(0)
print('NA')


from string import ascii_lowercase

def is_palindrome(string):
	return string == string[::-1]

def insert(string):
	as_list = list(string)
	for c in ascii_lowercase:
		for i in range(0, len(string)):
			as_list.insert(i, c)
			if is_palindrome(''.join(as_list)):
				return ''.join(as_list)
			as_list.pop(i)
		if is_palindrome(string + c):
			return string + c
	return 'NA'
s = input()
result = insert(s)
if result == 'NA':
	print('NA')
else:
	print(result)


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

def allway(s):
	flag = 0
	for i in range(len(s) + 1):
		for j in alf:
			new = s[:i] + j + s[i:]
			if isPal(new):
				flag = 1
				return new
	if flag == 0:
		return 'NA'
alf = 'abcdefghijklmnopqrstuvwxyz'
s = input()
print(allway(s))


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')


from collections import deque
import math
s = str(input())
n = len(s)
(d, d2) = (deque(), deque())
(ans, skip) = (0, 0)
for i in range(len(s)):
	d.append(s[i])
	d2.appendleft(s[i])
if ''.join(d) == ''.join(d2):
	d.insert(math.ceil(n / 2), s[math.ceil(n / 2) - 1])
	print(''.join(d))
	skip = 1
for i in range(len(s)):
	del d[i]
	del d2[n - 1 - i]
	s1 = ''.join(d)
	s2 = ''.join(d2)
	if s1 == s2:
		d.insert(i, s[i])
		if i >= n // 2:
			d.insert(n - i - 1, s[i])
		else:
			d.insert(n - i, s[i])
		ans = 1
		break
	else:
		d.insert(i, s[i])
		d2.insert(len(s) - 1 - i, s[i])
s3 = ''.join(d)
if ans == 0 and skip == 0:
	print('NA')
elif skip == 0:
	print(s3)


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)


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()

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')


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))


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')


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')