Substring of a Palindrome#11524
Some generous person has kindly given you a string consisting of lowercase English letters. You are asked to insert exactly lowercase English letters into 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 "codeforces" are not.) You can choose any lowercase English letters, and insert each of them to any position of , possibly to the beginning or the end of . You must insert exactly letters even if it is possible to turn into a palindrome by inserting less than letters.
Find the number of the palindromes that can be obtained in this way, modulo .
The first line contains a string s~(1 \le |s| \le 200). Each character in is a lowercase English letter.
The second line contains an integer n~(1 \le n \le 10^9).
Print the number of the palindromes that can be obtained, modulo .
For the first sample, you can obtain the palindrome "reviver" by inserting 'r' to the end of "revive".
For the second sample, the following palindromes can be obtained: "adada", "adbda", ..., "adzda", "dadad" and "ddadd".
Beispiel 1
Beispiel 2