E. Mr. Kitayuta's Gifttime limit per test6 secondsmemory limit per test768 megabytesinputstandard inputoutputstandard outputMr. 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.InputThe 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).OutputPrint the number of the palindromes that can be obtained, modulo 10007.ExamplesInputrevive1Output1Inputadd2Output28NoteFor 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".
Inputrevive1
Output1
['combinatorics', 'dp', 'matrices', 'strings', '*3000']