codechef Recipe Reconstruction 題解

chef had an interesting dream last night. he dreamed of a new revolutionary chicken recipe. when he woke up today he tried very hard to reconstruct the ingredient list. but, he could only remember certain ingredients. to simplify the problem, the ingredient

list can be represented by a string of lowercase characters ‘a‘ - ‘z‘.

chef can recall some characters of the ingredient list, all the others, he has forgotten. however, he is quite sure that the ingredient list was a palindrome.

you are given the ingredient list chef dreamed last night. the forgotten characters are represented by a question mark (‘?‘). count the number of ways chef can replace the forgotten characters with characters ‘a‘ - ‘z‘ in such a way that resulting ingredient

list is a palindrome.

the first line of input contains a single integer t, the number of test cases. t lines follow, each containing a single non-empty string - the ingredient list as recalled by chef. whatever letters he couldn‘t recall are represented by a ‘?‘.

for each test case, output a single line containing the number of valid ways the ingredient list could be completed. since the answers can be very large, output each answer modulo 10,000,009.

數學計算問題。

注意：

1 模的操作： 乘積的模等于模的乘積， 和的模等于模的和再模等操作

可以巧妙的簡化為一個計算了：

有？的時候，兩邊相等*26， 不等就為零了