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

Solution (in JAVA):

Solution:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;


public class codeforces_a_505 {

    static class FastScanner{
        BufferedReader s;
        StringTokenizer st;
        
        public FastScanner(){
            st = new StringTokenizer("");
            s = new BufferedReader(new InputStreamReader(System.in));
        }
        
        public FastScanner(File f) throws FileNotFoundException{
            st = new StringTokenizer("");
            s = new BufferedReader (new FileReader(f));
        }
        
        public int nextInt() throws IOException{
            if(st.hasMoreTokens())
                return Integer.parseInt(st.nextToken());
            else{
                st = new StringTokenizer(s.readLine());
                return nextInt();
            }
        }
        
      public double nextDouble() throws IOException{
            if(st.hasMoreTokens())
                return Double.parseDouble(st.nextToken());
            else{
                st = new StringTokenizer(s.readLine());
                return nextDouble();
            }
        }
      
        public long nextLong() throws IOException{
            if(st.hasMoreTokens())
                return Long.parseLong(st.nextToken());
            else{
                st = new StringTokenizer(s.readLine());
                return nextLong();
            }
        }
        
        public String nextString() throws IOException{
            if(st.hasMoreTokens())
                return st.nextToken();
            else{
                st = new StringTokenizer(s.readLine());
                return nextString();
            }
            
        }
        public String readLine() throws IOException{
            return s.readLine();
        }
        
        public void close() throws IOException{
            s.close();
        }
        
    }
      private static FastScanner s = new FastScanner();   
      private static PrintWriter ww = new PrintWriter(new OutputStreamWriter(System.out));
     
      static int count=0;
     public static void main(String[] args) throws IOException 
     {
        String ss = s.nextString();
        StringBuffer sd = new  StringBuffer(ss);
        String rev = sd.reverse().toString();
        if(pal(ss))
        {  
            if(ss.length()%2==0)
            {   System.out.println(""+ss.substring(0,ss.length()/2)+"y"+ss.substring(ss.length()/2,ss.length()));
            }
            else
            {
                  
                  sd.append(ss.charAt(0));
                  if(pal(sd.toString()))
                      System.out.println(""+sd.toString());
                  else
                  {
                      int rm=ss.length()/2;
                     String h=ss.substring(0,rm+1)+ss.substring(rm,rm+2)+ss.substring(rm+2,ss.length());
                      //System.out.println("--->"+h);
                     if(pal(h))
                     System.out.println(""+h);  
                     else
                      System.out.println("NA");    
                  }
                          
            }
        }
        else 
        {
           String dg=mpal(ss); 
            //System.out.println("----> "+dg);
           if(pal(dg))
           {
               System.out.println(""+dg);
           }
           else
           {
               System.out.println("NA");
           }
        }
         
         s.close();
         ww.close();
     }
     public static boolean pal(String a)
     {
        StringBuffer sr = new StringBuffer(a);
        String rev = sr.reverse().toString();
        if(rev.equals(a))
            return true;
        else
            return false; 
     }   

        public static String mpal(String ss)
     {
        StringBuffer sr = new StringBuffer(ss);String ans="art";
        StringBuilder sb=new StringBuilder(ss);
        String rev = sr.reverse().toString();boolean arc=true;
        if(rev.charAt(0)!=ss.charAt(0))
        {
           ans=rev.substring(0,1)+ss;
           // System.out.println("now ans is "+ans);
          // ans=sb.toString();
            if(!pal(ans))
            {
                sb=new StringBuilder(ss);
                sb.append(ss.charAt(0));
                ans=sb.toString();
            }
               
        }  
        else
        {
          for(int i=0;i<ss.length();i++)
          {
              if(ss.charAt(i)!=rev.charAt(i))
              {
                  ans=rev.substring(0,i)+ss.substring(i,i+1)+rev.substring(i,ss.length());
                 
                 // System.out.println("now ans is "+ans+"  "+pal(ans));
                  if(!pal(ans))
                    ans=ss.substring(0,i)+rev.substring(i,i+1)+ss.substring(i,ss.length());  
                  break;
              }
          }
           // ans=sb.toString();
          
        }
        return ans;
     }
        public static int gcd(int a, int b){
        return b == 0 ? a : gcd(b,a%b);
    }

}
/*zabardast swappimng of sorting
/*
    for(int h=0;h<n;h++)
        {  int temp,temp1,temp2;
             for(int y=h+1;y<n;y++)
           {
             if(a[y][2]>=a[h][2])
             {
              
             temp=a[y][2];                 //////sorting
             a[y][2]=a[h][2]; 
              a[h][2]=temp;
              temp1=a[y][0];
              a[y][0]=a[h][0];
              a[h][0]=temp1;
              temp2=a[y][1];
              a[y][1]=a[h][1];
              a[h][1]=temp2;
           
             }
           }  
        }
*/
/*
static final Point getMinMax(int[] array) {
        int min = array[0];
        int max = array[0];
        
        for (int index = 0, size = array.length; index < size; ++index, ++index) {
            int value = array[index];
            
            if (index == size - 1) {
                min = min(min, value);
                max = max(max, value);
            } else {
                int otherValue = array[index + 1];
                
                if (value <= otherValue) {
                    min = min(min, value);
                    max = max(max, otherValue);
                } else {
                    min = min(min, otherValue);
                    max = max(max, value);
                }
            }
        }
        
        return new Point(min, max);
    }
    
*/
/*

/// Demonstrate several Is... methods.
class IsDemo {
public static void main(String args[]) {
char a[] = {'a', 'b', '5', '?', 'A', ' '};
for(int i=0; i<a.length; i++) {
if(Character.isDigit(a[i]))                                   ///check if digit is present in string
System.out.println(a[i] + " is a digit.");
if(Character.isLetter(a[i]))
    System.out.println(num + " in binary: " +
Integer.toBinaryString(num));
System.out.println(num + " in octal: " +
Integer.toOctalString(num));
System.out.println(num + " in hexadecimal: " +
Integer.toHexString(num));
}
}
*/
/*
private static void findSubsets(int array[])
{
  int numOfSubsets = 1 << array.length; 

  for(int i = 0; i < numOfSubsets; i++)
 {
    int pos = array.length - 1;                                /////bitmask to find all sub sets
   int bitmask = i;

   System.out.print("{");
   while(bitmask > 0)
   {
    if((bitmask & 1) == 1)
     System.out.print(array[pos]+",");
    bitmask >>= 1;
    pos--;
   }
   System.out.print("}");
 }
}
*/

/*   no of DIVISORSSSSSS
 public ArrayList<Integer> get(int x){
            ArrayList<Integer> divisors = new ArrayList<>();
            for(int i = 1; i * i <= x; i++){
                if(x % i == 0){
                    divisors.add(i);
                    if(i * i != x){
                        divisors.add( x / i);
                    }
                }
            }
            
*/
/*  //// find sum of multiple of a value below limit// ----> (l*(n+1))/2
  public static long getSequenceSum(long value, long limit) {
long q = (limit - 1) / value;
long ans = ((value*q)*(1+q) )/ 2;
return ans;
}
*/
/*// largest prime factor of a no
 public static long largestPrimeFactor(long n) {

        // largest composite factor must be smaller than sqrt
        long sqrt = (long)Math.ceil(Math.sqrt((double)n));

        long largest = -1;

        for(long i = 2; i <= sqrt; i++) {
            if(n % i == 0) {
                long test = largestPrimeFactor(n/i);
                if(test > largest) {
                    largest = test;
                }
            }
        }

        if(largest != -1) {
            return largest;
        }

        // number is prime
        return n;
    } 
*/
/*    // prime no using sieve of erostheneses
  public static void prime()
{
  boolean[] isPrime = new boolean[100000000+ 1];
         Arrays.fill(isPrime, true);

        // mark non-primes <= N using Sieve of Eratosthenes
        for (int i = 2; i*i <= 100000000; i++)
        {

             if (isPrime[i])
             {
                for (int j = i; i*j <= 100000000; j++) {
                    isPrime[i*j] = false;
                }^
            }
        }
}

*/