Problem: 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.

Solution (in JAVA):

Solution:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import java.util.StringTokenizer;
import javax.swing.RowFilter;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        //StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        String str = reader.readLine();
        char a = 'a';
        char z = 'z';
        search:
        for (char ch = a; ch <= z; ch++) {
            for (int i = 0; i <= str.length(); i++) {
                StringBuilder builder;
                if (i == 0) {
                    builder = new StringBuilder(ch + str);
                } else if (i == str.length()) {
                    builder = new StringBuilder(str + ch);
                } else {
                    builder = new StringBuilder(str.substring(0, i) + ch + str.substring(i));
                }
                if(builder.toString().equals(builder.reverse().toString())){
                    System.out.println(builder);
                    System.exit(0);
                }
            }
        }
        System.out.println("NA");
    }

    static BigInteger[] Dp2Combination(int N) {
        int i, j;
        BigInteger[] Combination = new BigInteger[N + 1];
        for (i = 0; i <= N/**/ / 2; i++) {
//            for (j = i; j >= 0; j--) {
//                if (j == 0 || j == i) {
//                    Combination[ j] = 1;
//                } else {
//                    Combination[ j] = Combination[ j] + Combination[ j - 1];
//                }
//            }
            Combination[i] = Algorithm.C(new BigInteger(String.format("%d", N)), new BigInteger(String.format("%d", i)));
        }
        return Combination;
    }

    private static long[] Fib(int i) {
        long[] a = new long[i];
        a[0] = a[1] = 1;
        for (int j = 2; j < i; j++) {
            a[j] = a[j - 1] + a[j - 2];
        }
        return a;


    }

    static class Algorithm {

        static class MyString {

            static int NumberOfIterations(String str, String p) {
                int sum = 0;

                int index = 0;
                while (true) {
                    int temp = str.substring(index).indexOf(p);
                    if (temp >= 0) {
                        index += (temp + p.length());
                        sum++;
                    } else {
                        break;
                    }
                }

                return sum;
            }
        }

        static HashSet<Integer> NumbersFrom(String digitsString) {
            int[] digits = new int[10];
            for (int i = digitsString.length() - 1; i >= 0; i--) {
                if (digitsString.charAt(i) >= '0' && digitsString.charAt(i) <= '9') {
                    digits[digitsString.charAt(i) - '0']++;
                }
            }
            return NumbersFrom(digits);
        }

        static HashSet<Integer> NumbersFrom(int[] digits) {
            int maxDigit = 0;
            for (int i = 0; i < digits.length; i++) {
                maxDigit += digits[i];
            }
            return NumbersFrom(digits, maxDigit);
        }

        static HashSet<Integer> NumbersFrom(int[] digits, int maxDigit) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < digits.length; i++) {
                if (digits[i] > 0) {
                    list.add(i);
                }
            }
            int t1 = 0;
            int t2 = list.size();
            for (int i = 1; i < maxDigit; i++) {
                for (int j = t1; j < t2; j++) {
                    int number = list.get(j);
                    int temp = number;
                    while (temp > 0) {
                        digits[temp % 10]--;
                        temp /= 10;
                    }
                    for (int k = 0; k < 10; k++) {
                        if (digits[k] > 0) {
                            list.add(number * 10 + k);
                        }
                    }
                    while (number > 0) {
                        digits[number % 10]++;
                        number /= 10;
                    }
                }
                t1 = t2;
                t2 = list.size();
            }
            HashSet<Integer> set = new HashSet<Integer>(list);
            return set;
        }

        static long C(int n, int r) {
            if (n == 0) {
                return 1;
            }
            if (r == 0) {
                return 1;
            }
            if (n == r) {
                return 1;
            }
            if (r < n / 2) {
                return C(n, n - r);
            }
            return ZarbeMotevali(r + 1, n) / Fact(n - r);
        }

        static BigInteger C(BigInteger n, BigInteger r) {
            if (n.compareTo(new BigInteger("0")) == 0) {
                return new BigInteger("1");
            }
            if (r.compareTo(new BigInteger("0")) == 0) {
                return new BigInteger("1");
            }
            if (n.compareTo(r) == 0) {
                return new BigInteger("1");
            }
            if (r.compareTo(n.divide(new BigInteger("2"))) < 0) {
                return C(n, n.add(r.multiply(new BigInteger("-1"))));
            }
            return ZarbeMotevali(r.add(new BigInteger("1")), n).divide(ZarbeMotevali(new BigInteger("1"), n.add(r.multiply(new BigInteger("-1")))));
        }

        private static long ZarbeMotevali(int first, int end) {
            long answer = 1;
            for (long i = first; i <= end; i++) {
                answer *= i;
            }
            return answer;
        }

        private static BigInteger ZarbeMotevali(BigInteger first, BigInteger end) {
            BigInteger answer = new BigInteger("1");
            for (BigInteger i = new BigInteger(first.toString()); i.compareTo(end) <= 0; i = i.add(new BigInteger("1"))) {
                answer = answer.multiply(i);
            }
            return answer;
        }

        /**
         * **********************************
         */
        static <T> List<List<T>> getSublists(List<T> list) {
            if (list.isEmpty()) {
                return Collections.singletonList(list);
            } else {
                List<List<T>> sublists = new ArrayList<List<T>>();
                T first = list.get(0);
                for (List<T> sublist : getSublists(list.subList(1, list.size()))) {
                    List<T> sublistWithFirst = new ArrayList<T>();
                    sublistWithFirst.add(first);
                    sublistWithFirst.addAll(sublist);
                    sublists.add(sublist);
                    sublists.add(sublistWithFirst);
                }
                return sublists;
            }
        }

        private static long Fact(int n) {
            return ZarbeMotevali(2, n);
        }

        static int GCD(int m, int n) {
            if (n > m) {
                return GCD(n, m);
            }
            if (m % n == 0) {
                return n;
            }
            return GCD(n, m % n);
        }

        static long GCD(long m, long n) {
            if (n > m) {
                return GCD(n, m);
            }
            if (m % n == 0) {
                return n;
            }
            return GCD(n, m % n);
        }

        static long LCM(long m, long n) {
            return (m * n) / GCD(m, n);
        }

        static int LCM(int m, int n) {
            return (m * n) / GCD(m, n);
        }

        static boolean IsPrime(long a) {
            if (a < 2) {
                return false;
            }
            if (a > 2 && a % 2 == 0) {
                return false;
            }
            long temp = (long) Math.sqrt(a);
            for (long i = 3; i <= temp; i += 2) {
                if (a % i == 0) {
                    return false;
                }
            }
            return true;
        }

        static int BinarySearch(int[] a, int start, int end, int value) {
            if (start == end) {
                return -1; // invalid index
            }
            int mid = (end + start) / 2;
            if (a[mid] == value) {
                return mid;
            }
            if (a[mid] < value) {
                return BinarySearch(a, mid + 1, end, value);
            }
            return BinarySearch(a, start, mid, value);
        }
    }
}

class MyPoint {

    double x;
    double y;

    public MyPoint(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public double distance(MyPoint point) {
        return Math.sqrt(Math.pow(this.x - point.x, 2) + Math.pow(this.y - point.y, 2));
    }

    public void change(double newX, double newY) {
        this.x = newX;
        this.y = newY;
    }
}

class Graph {

    private int[][] matrix;

    public Graph(int[][] matrix) {
        this.matrix = matrix;
    }

    class SortestPath {

        private int minDistance(long[] dist, boolean[] sptSet) {
            // Initialize min value
            long min = Long.MAX_VALUE;
            int minIndex = 0;

            for (int i = 0; i < matrix.length; i++) {
                if (sptSet[i] == false && dist[i] <= min) {
                    min = dist[i];
                    minIndex = i;
                }
            }

            return minIndex;
        }

        public long[] Dijkstra(int src) {
            int n = matrix.length;
            long[] dist = new long[n];

            boolean[] sptSet = new boolean[n];
            Arrays.fill(dist, Long.MAX_VALUE);
            Arrays.fill(sptSet, false);

            dist[src] = 0;

            for (int count = 0; count < n - 1; count++) {
                int u = minDistance(dist, sptSet);

                sptSet[u] = true;

                for (int i = 0; i < n; i++) {
                    if (!sptSet[i] && matrix[u][i] != 0 && dist[u] != Long.MAX_VALUE
                            && dist[u] + matrix[u][i] < dist[i]) {
                        dist[i] = dist[u] + matrix[u][i];
                    }
                }
            }
            return dist;
        }
    }

    class MST {

        class Prim {

            private boolean[] Visited;
            //private 
        }
    }

    class DFS {

        private Stack<Integer> DFS;
        private boolean[] visited;

        public DFS() {
            this.DFS = new Stack<Integer>();
            this.visited = new boolean[matrix.length];
        }

        public Stack<Integer> getDFS() {
            this.DFS(0);
            return DFS;
        }

        public Stack<Integer> getDFS(int vertex) {
            this.DFS.clear();
            this.DFS(vertex);
            return this.DFS;
        }

        private void DFS(int vertrx) {
            this.DFS.push(vertrx);
            this.visited[vertrx] = true;

            for (int i = 0; i < matrix[vertrx].length; i++) {
                if (matrix[vertrx][i] != 0 && !this.visited[i] && vertrx != i) {
                    this.DFS(i);
                }
            }
        }
    }
}

class ArithmeticProgression {

    long d;
    long a1;

    public ArithmeticProgression(long a1, long d) {
        this.d = d;
        this.a1 = a1;
    }

    public ArithmeticProgression(long a, long index, long d) {
        this.d = d;
        this.a1 = a - ((index - 1) * d);
    }

    long Term(long n) {
        return this.a1 + ((n - 1) * this.d);
    }

    long S(long n) {
        return S(1, n);
    }

    long S(long m, long n) {
        return ((n - m + 1) * (Term(m) + Term(n))) / 2;
    }
}

class FastScanner {

    private InputStream stream;
    private byte[] buffer = new byte[1024];
    private int curChar;
    private int numChars;

    public FastScanner(InputStream stream) {
        this.stream = stream;
    }

    int read() {
        if (numChars == -1) {
            throw new InputMismatchException();
        }
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buffer);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0) {
                return -1;
            }
        }
        return buffer[curChar++];
    }

    boolean isWhiteSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    boolean isEndline(int c) {
        return c == '\n' || c == '\r' || c == -1;
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    float nextFloat() {
        return Float.parseFloat(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String next() {
        int c = read();
        while (isWhiteSpaceChar(c)) {
            c = read();
        }
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isWhiteSpaceChar(c));
        return res.toString();
    }

    String nextLine() {
        int c = read();
        while (isEndline(c)) {
            c = read();
        }
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isEndline(c));
        return res.toString();
    }
}