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.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.util.Objects;
import java.util.StringTokenizer;

public class Main {

  public static void main(String[] args) throws IOException {
    IOScanner scanner;
    if (new File("data.in").exists()) {
      scanner = new IOScanner("data.in", null);
    } else {
      scanner = new IOScanner();
    }
    while (scanner.hasNext()) {
      new Solver(scanner).solve();
    }
    scanner.close();
  }
}

class IOScanner {
  private final BufferedReader reader;
  private final PrintWriter writer;
  private StringTokenizer stringTokenizer;

  public IOScanner() {
    this(System.in, System.out);
  }

  public IOScanner(String input, String output) throws FileNotFoundException {
    this(input == null ? null : new File(input), output == null ? null : new File(output));
  }

  public IOScanner(File input, File output) throws FileNotFoundException {
    this(input == null ? System.in : new FileInputStream(input), output == null ? System.out
        : new FileOutputStream(output));
  }

  public IOScanner(InputStream inputStream, OutputStream outputStream) {
    reader = new BufferedReader(new InputStreamReader(inputStream));
    writer = new PrintWriter(outputStream);
  }

  private StringTokenizer read() {
    while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
      try {
        stringTokenizer = new StringTokenizer(reader.readLine());
      } catch (Exception e) {
        return null;
      }
    }
    return stringTokenizer;
  }

  public boolean hasNext() {
    StringTokenizer tokenizer = read();
    return tokenizer != null && tokenizer.hasMoreTokens();
  }

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

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

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

  public int[] nextInts(int n) {
    int[] input = new int[n];
    for (int i = 0; i < n; i++) {
      input[i] = nextInt();
    }
    return input;
  }

  public double[] nextDoubles(int n) {
    double[] input = new double[n];
    for (int i = 0; i < n; i++) {
      input[i] = nextDouble();
    }
    return input;
  }

  public String[] nexts(int n) {
    String[] input = new String[n];
    for (int i = 0; i < n; i++) {
      input[i] = next();
    }
    return input;
  }

  public char[][] nextCharArrays(int n) {
    String[] input = nexts(n);
    char[][] result = new char[n][];
    for (int i = 0; i < n; i++) {
      result[i] = input[i].toCharArray();
    }
    return result;
  }

  public String next() {
    return read().nextToken();
  }

  public void println() {
    writer.println();
  }

  public void println(Iterable<?> iterable) {
    println(iterable.iterator());
  }

  public void println(Iterator<?> iterator) {
    boolean first = true;
    while (iterator.hasNext()) {
      if (first) {
        first = false;
      } else {
        print(' ');
      }
      print(iterator.next());
    }
    println();
  }

  public void println(Object token) {
    writer.println(token);
  }

  public void print(Object token) {
    writer.print(token);
  }

  public void printf(String format, Object... args) {
    writer.printf(format, args);
  }

  public void flush() {
    writer.flush();
  }

  public void close() throws IOException {
    reader.close();
    writer.close();
  }
}

class Edge {
  final int from, to, type;
  boolean needed = false;
  final Edge next;
  final String s;

  Edge(int from, int to, int type, Edge next, String s) {
    this.from = from;
    this.to = to;
    this.type = type;
    this.next = next;
    this.s = s;
  }

  @Override
  public String toString() {
    return s;
  }

  @Override
  public boolean equals(Object other) {
    if (!(other instanceof Edge)) {
      return false;
    }
    Edge that = (Edge) other;
    return Objects.equals(this.s, that.s);
  }

  @Override
  public int hashCode() {
    return Objects.hash(s);
  }
}

class Solver {

  private final IOScanner scanner;

  public Solver(IOScanner scanner) {
    this.scanner = scanner;
  }

  public void solve() {
    String s = scanner.next();
    for (int i = 0; i <= s.length(); i++) {
      for (int j = 0; j < 26; j++) {
        StringBuilder sb = new StringBuilder().append(s);
        sb.insert(i, (char) (j + 'a'));
        char[] arr = sb.toString().toCharArray();
        boolean ok = true;
        for (int l = 0, r = arr.length - 1; l < r; l++, r--) {
          if (arr[l] != arr[r]) {
            ok = false;
            break;
          }
        }
        if (ok) {
          scanner.println(sb.toString());
          return;
        }
      }
    }
    scanner.println("NA");
  }
}