CF506E Mr. Kitayuta's Gift

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 $ .

N/A

N/A

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